Есть ли удобный способ использовать комбинаторы синтаксического анализатора Scala для анализа языков, в которых важны отступы? (например, питон)
Разбор языка на основе отступов с помощью комбинаторов парсера scala
Ответы (2)
Предположим, у нас есть очень простой язык, на котором это корректная программа.
block
inside
the
block
и мы хотим проанализировать это в List[String]
с каждой строкой внутри блока как один String
.
Сначала мы определяем метод, который принимает минимальный уровень отступа и возвращает синтаксический анализатор для строки с этим уровнем отступа.
def line(minIndent:Int):Parser[String] =
repN(minIndent + 1,"\\s".r) ~ ".*".r ^^ {case s ~ r => s.mkString + r}
Затем мы определяем блок с минимальным уровнем отступа, повторяя синтаксический анализатор строк с подходящим разделителем между строками.
def lines(minIndent:Int):Parser[List[String]] =
rep1sep(line(minIndent), "[\n\r]|(\n\r)".r)
Теперь мы можем определить синтаксический анализатор для нашего маленького языка следующим образом:
val block:Parser[List[String]] =
(("\\s*".r <~ "block\\n".r) ^^ { _.size }) >> lines
Сначала он определяет текущий уровень отступа, а затем передает его как минимум синтаксическому анализатору строк. Давайте проверим это:
val s =
"""block
inside
the
block
outside
the
block"""
println(block(new CharSequenceReader(s)))
И мы получаем
[4.10] parsed: List( inside, the, block)
Чтобы все это скомпилировалось, вам нужны эти импорты
import scala.util.parsing.combinator.RegexParsers
import scala.util.parsing.input.CharSequenceReader
И вам нужно поместить все в объект, который расширяет RegexParsers
вот так
object MyParsers extends RegexParsers {
override def skipWhitespace = false
....
Из того, что я знаю, нет, комбинаторы парсеров Scala не поддерживают такие вещи из коробки. Вы, безусловно, можете сделать это, осмысленно анализируя пустое пространство, но вы столкнетесь с некоторыми проблемами, поскольку вам нужна какая-то форма конечного автомата для отслеживания стека отступов.
Я бы порекомендовал сделать шаг предварительной обработки. Вот небольшой препроцессор, который добавляет маркеры к отдельным блокам с отступом:
object Preprocessor {
val BlockStartToken = "{"
val BlockEndToken = "}"
val TabSize = 4 //how many spaces does a tab take
def preProcess(text: String): String = {
val lines = text.split('\n').toList.filterNot(_.forall(isWhiteChar))
val processedLines = BlockStartToken :: insertTokens(lines, List(0))
processedLines.mkString("\n")
}
def insertTokens(lines: List[String], stack: List[Int]): List[String] = lines match {
case List() => List.fill(stack.length) { BlockEndToken } //closing all opened blocks
case line :: rest => {
(computeIndentation(line), stack) match {
case (indentation, top :: stackRest) if indentation > top => {
BlockStartToken :: line :: insertTokens(rest, indentation :: stack)
}
case (indentation, top :: stackRest) if indentation == top =>
line :: insertTokens(rest, stack)
case (indentation, top :: stackRest) if indentation < top => {
BlockEndToken :: insertTokens(lines, stackRest)
}
case _ => throw new IllegalStateException("Invalid algorithm")
}
}
}
private def computeIndentation(line: String): Int = {
val whiteSpace = line takeWhile isWhiteChar
(whiteSpace map {
case ' ' => 1
case '\t' => TabSize
}).sum
}
private def isWhiteChar(ch: Char) = ch == ' ' || ch == '\t'
}
Выполнение для этого текста дает:
val text =
"""
|line1
|line2
| line3
| line4
| line5
| line6
| line7
| line8
| line9
|line10
| line11
| line12
| line13
""".stripMargin
println(Preprocessor.preProcess(text))
... следующий результат
{
line1
line2
{
line3
line4
line5
{
line6
line7
}
}
{
line8
line9
}
line10
{
line11
line12
line13
}
}
И послесловие вы можете использовать библиотеку комбинатора, чтобы сделать синтаксический анализ более простым способом.
Надеюсь это поможет