Какой тип парсера нужен для этой грамматики? - PullRequest
Новая
       34

Какой тип парсера нужен для этой грамматики?

5 голосов
/ 16 октября 2011

У меня есть грамматика, которую я не знаю, какой тип синтаксического анализатора мне нужен для его анализа, кроме того, что я не верю, что грамматика - это LL (1).Я думаю, что мне нужен парсер с возвратом или LL (*) какой-то.Придуманная мной грамматика (которая может потребовать некоторого переписывания): 

S: Rules
Rules: Rule | Rule Rules
Rule: id '=' Ids
Ids: id | Ids id

Язык, который я пытаюсь создать, выглядит примерно так: 

abc = def g hi jk lm
xy = aaa bbb ccc ddd eee fff jjj kkk
foo = bar ha ha

Ноль или более Правилокоторые содержат левый идентификатор, за которым следует знак равенства, за которым следует один или несколько идентификаторов.Часть, для которой у меня возникнут проблемы при написании парсера, заключается в том, что грамматика допускает любое количество идентификатора в правиле, и что единственный способ узнать, когда начинается новое правило, - это когда он находит id =, что потребовало бы возврата.

Кто-нибудь знает классификацию этой грамматики и лучший метод синтаксического анализа для написанного от руки синтаксического анализатора?

1 Ответ

4 голосов
/ 16 октября 2011

Грамматика, которая генерирует идентификатор, за которым следует знак равенства, за которым следует конечная последовательность идентификаторов, является регулярным . Это означает, что строки в языке могут быть проанализированы с использованием DFA или регулярного выражения. Нет необходимости в причудливых недетерминированных или LL (*) парсерах.

Чтобы убедиться, что язык правильный, пусть Id = U { a : a ∈ Γ}, где Γ ⊂ Σ - набор символов это может произойти в идентификаторах. Язык, который вы пытаетесь создать, обозначается регулярным выражением

  • Id + = ( Id + ) * Id +

Установка Γ = { a , b , ..., z }, примеры строк на языке регулярного выражения:

  • смотри = я на обычном языке
  • эй = это означает, что меня может узнать dfa
  • круто = или даже регулярное выражение

Нет необходимости анализировать ваш язык, используя мощные методы синтаксического анализа. Это один из случаев, когда разбор с использованием регулярных выражений или DFA уместен и оптимален.

редактирование:

Назовите указанное выше регулярное выражение R . Для анализа R * создайте DFA, распознающий язык R *. Для этого сгенерируйте NFA, распознающий язык R *, используя алгоритм, полученный из теоремы Клини. Затем преобразуйте NFA в DFA, используя конструкцию подмножества. Результирующий DFA распознает все строки в R *. Учитывая представление сконструированного DFA на языке реализации, необходимые действия - например,

  • Добавить последний проанализированный идентификатор в правую часть текущего оператора объявления, который анализируется
  • Добавьте последний разобранный оператор объявления в список проанализированных объявлений и используйте последний проанализированный идентификатор, чтобы начать синтаксический анализ нового оператора объявления

может быть закодировано в состояния DFA. В действительности, использование теоремы Клини и конструкции подмножества, вероятно, не требуется для такого простого языка. То есть вы, вероятно, можете просто написать синтаксический анализатор с двумя вышеупомянутыми действиями без реализации автомата. Учитывая более сложный регулярный язык (например, лексическую структуру языка программирования), преобразование будет лучшим вариантом.

...