Разбор языка - как работать с несколькими опциями в правиле - PullRequest
Новая
       84

Разбор языка - как работать с несколькими опциями в правиле

0 голосов
/ 23 февраля 2020

Я пишу парсер языка. Он основан на правилах стиля BNF, где правило содержит список опций или терминальных токенов. Например: 

# Rule A matches the current token stream position if it matches rule B
# followed by rule C followed by a semicolon
rule_a:
  rule_b rule_c ";"

# Rule B matches the current token stream position if the token 
# there equals "foo"
rule_b:
  "foo"

# Rule C matches the current token stream position if it matches
# either rule D or rule E
rule_c:
  rule_d | rule_e

rule_d:
  "bar"

rule_e:
  "bar bar"

Проблема, с которой я сталкиваюсь, заключается в том, что если при разборе правила C ОБА правила D и E соответствуют текущему потоку токенов, но только позже (прогресс в Правило A) Становится ли очевидным, что только один из D или E был правильным выбором? При повторном обращении к синтаксическому дереву такого типа создается впечатление, что историю необходимо каким-то образом сохранить, чтобы можно было «повторить попытку» обход конкретного синтаксического дерева, но с другими параметрами, чем в прошлый раз.

Как Например, используя приведенные выше правила, что, если я пытаюсь проанализировать следующий текст: 

foo bar bar;

Дерево вызовов обхода выглядит следующим образом, здесь используются отступы для отображения глубины рекурсии. 

parse(token = "foo", rule = rule_a)
  parse(token = "foo", rule = rule_b)
    parse(token = "foo", rule = terminal_token("foo")
      success: consume "foo", return true
    success: return true
  // So far so good, keep going with rule_a
  parse(token = "bar", rule = rule_c)
    parse(token = "bar", rule = rule_d) // Try rule D first.
      parse(token = "bar", rule = terminal_token("bar")
        success: consume "bar", return true
      success: return true
    success: return true // Rule D matched.
  // Still good, keep going.      
  parse(token = "bar", rule = terminal token ";") // second "bar" here
    fail: return false // "bar" != ";"
  fail: return false. // Sequence rule_b rule_c ";" did not match

Таким образом, теперь синтаксический анализ не удался, даже несмотря на то, что он был бы успешным, если бы было опробовано правило E вместо правила D. У меня возникли проблемы с поиском хорошего способа отследить, какие правила были опробованы на каком токене. Если правило A в конечном итоге терпит неудачу, как показано выше, его действительно следует повторить, на этот раз попробуйте другие параметры в некоторых из подчиненных правил - в этом случае выбирается второй параметр (rule_e) при синтаксическом анализе rule_ c. Но это усложняется очень быстро - с более сложными грамматиками могут быть длинные цепочки правил, каждая с несколькими вариантами. Поэтому мне неясно, как вы узнали бы из неудачного результата разбора, были ли другие способы, которые могли бы быть проанализированы, а затем, как исчерпывающе попробовать их все.

1 Ответ

2 голосов
/ 23 февраля 2020

Только очень небольшое подмножество грамматик может быть проанализировано с помощью интеллектуального синтаксического анализатора. Иногда вы можете перетасовать свою грамматику таким образом, чтобы она стала разбираемой, но обычно это требует затрат: грамматика становится труднее читать и / или не может точно представить структуру языка syntacti c. Как вы говорите, откат возможен, но требует определенного объема бухгалтерии и может немного замедлить синтаксический анализ.

Так что обычно лучше оставить грамматику такой, какая она есть, и выбрать другой алгоритм синтаксического анализа, один который может исследовать более чем одну возможность одновременно.

Если вам повезет, ваша грамматика может оказаться LALR (1), что является гораздо большим набором языков, чем набор, который может быть разбирается с прогнозирующим парсером без возврата. Многие языки программирования имеют достаточно простые грамматики LALR (1) или, по крайней мере, достаточно близки, чтобы их можно было использовать, а затем отклонять случайный ошибочный ввод при проверке дерева разбора.

Для других языков вы может использовать один из обобщенных методов синтаксического анализа, который исследует все возможные синтаксические анализы параллельно, поддерживая более сложный стек синтаксического анализа для эффективного представления различных потенциальных синтаксических анализов. Один такой алгоритм был предложен в 1968 году [Джей Эрли]; современные вариации включают парсеры GLR и GLL.

Существует множество генераторов парсеров, которые могут создавать эффективные парсеры для множества таких подходов. Таким образом, нет необходимости записывать все вручную, но если вы хотите присвоить ему go, алгоритм Эрли достаточно прост.

...