LL-грамматика с ассоциативностью и самостоятельной ссылкой

Question

Я пытаюсь написать грамматику парсера и в настоящее время имею следующие произведения для грамматики LL (в Antlr), и я пытаюсь разобрать один или несколько (числа или строки), которые разделены с помощью «#», который является правильным ассоциативным. Как мне изменить производственные процессы, чтобы он мог анализировать одну или несколько строк, разделенных «#», а не только одну на данный момент?

A ::= B 
    | Number 
    | String 

B ::= C "->" A 

C ::= Number 
    | String 

Примеры языков для этой грамматики:

ABC# 123 
123 # ABC 
ABC# DEF # 123 
ABC# DEF # (123 # 456) 
ABC# (DEF # 123) # 456 

Я попытался с помощью формы EBNF

A ::= B 
    | Number 
    | String 
    | "(" A ")" 

B ::= C ("#" A)? 

C ::= Number 
    | String 

Но что заставляет мое Grammar быть неоднозначным. Как я могу исправить эту двусмысленность?

Answer 1

Неоднозначность исходит из того, вы можете получить Number или String два пути - либо непосредственно A ->Number или A ->B ->C ->Number (и аналогично для String). Очевидное исправление избавиться от прямых производств:

A ::= B 
    | "(" A ")" 

B ::= C ("#" A)? 

C ::= Number 
    | String 

Answer 2

Я думаю, что вы ищете совсем немного проще:

A ::= B ("#" B)* 
B ::= Number | String | "(" A ")" 

Не будучи ANTLR профессионал, я не конечно, как бы вы пометили # как право-ассоциативный, но цель этого правила состоит в том, чтобы создать список B, так что вы могли бы предположительно связать их справа в семантическом правиле.

Важно поставить правило выражения в скобки в нижней части иерархии (так сказать); в противном случае вы не сможете разобрать (first # second) # third.