Параметр грамматики разбора и повторения

Question

Я смог добавить поддержку грамматики моего парсера для чередующихся символов (например, ababa или baba), следуя вместе с this question.

Теперь я хочу расширить это, разрешив повторы символов.

Например, я хотел бы иметь возможность поддерживать abaaabab и aababaaa. В моем частном случае разрешается повторять только a, но также полезно использовать решение, которое допускает повторение b.

Учитывая правила от другого вопроса:

expr ::= A | B 
A ::= "a" B | "a" 
B ::= "b" A | "b" 

... Я попытался распространить его на поддержку повторы, например, так:

expr ::= A | B 

# support 1 or more "a" 
A_one_or_more = A_one_or_more "a" | "a" 

A ::= A_one_or_more B | A_one_or_more 
B ::= "b" A | "b" 

... но грамматика неоднозначна. Возможно ли, чтобы это стало однозначным, и если бы кто-нибудь мог мне помочь устранить его?

Я использую lemon parser, который является парсером LALR (1).

Answer 1

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

Например, язык, который состоит из произвольных повторений a и b могут быть описаны с регулярным выражением (a|b)*, которое может быть записано в BNF, как

S ::= /* empty */ | S a | S b 

Но это, вероятно, не захватить синтаксическую структуру вы пытаетесь оттолкнуть. С другой стороны, поскольку вы не указываете эту структуру, ее трудно понять.

Вот несколько больше возможностей, которые строят различные деревья разбора:

S ::= E | S E 
E ::= A b | E b 
A ::= a | A a 

---

S ::= E | S E 
E ::= A B 
A ::= a | A a 
B ::= b | B b 

При написании грамматики для синтаксического анализа языка, полезно начать с рисования ваши предложенные деревьев разбора , Обычно вы можете написать грамматику непосредственно из формы деревьев, что показывает, что формальная грамматика в основном представляет собой инструмент , так как он четко описывает язык таким образом, что неофициальные описания не могут. Использование генератора синтаксического анализатора для преобразования этой грамматики в парсер гарантирует, что синтаксический анализатор реализует описанный язык. Или, по крайней мере, это цель.

Answer 2

Вот хороший инструмент для проверки вашей грамматики онлайн http://smlweb.cpsc.ucalgary.ca/start.html. Он фактически принимает the grammar you provided как допустимую грамматику LALR (1).

Другой LALR (1) грамматики, что позволяет reapeating элементов а, была бы:

S ::= "a" S | "a" | "b" A | "b" 
A ::= "a" S .