Манипулировать следующей грамматикой, чтобы быть LL (1)

Предположим, мне дали следующую грамматику:

start -> statement //cannot change

statement ->  assignment SEMICOLON

statement ->  function_call SEMICOLON

assignment ->  IDENTIFIER EQUAL expression

function_call ->  IDENTIFIER LPAREN parameters RPAREN SEMICOLON

Грамматика прямо сейчас не может быть LL (1), потому что нетерминалы для оператора (назначение и вызов_функции) оба имеют IDENTIFIER в качестве первого терминала для каждого своего производства. Только с помощью 2-х упреждающих действий вы можете решить, по какому пути пойдет синтаксический анализатор.

Есть ли способ манипулировать приведенной выше грамматикой, чтобы она была LL (1)? Или это невозможно?


parsing grammar ll
person Jebathon    schedule 20.10.2016    source источник
comment
Левый факторинг должен быть легким для поиска. Подсказка: statement: IDENTIFIER rest; rest: something | something-else   -  person rici    schedule 20.10.2016
comment
@rici Я понимаю, но если бы у вас было что-то вроде [оператор -> составное_оператор] и [составное_оператор -> задание | function_call] будет ли это по-прежнему считаться LL(1)?   -  person Jebathon    schedule 21.10.2016
comment
нет, не будет. Чтобы быть LL(1), вам нужно знать, какое производство будет расширено, глядя на следующие (1) жетоны. Следующим токеном будет IDENTIFIER, и это позволит вам предсказать statement -> compound_statement, но не то, какое из двух compound_statement произведений. Поэтому вам нужно использовать левый фактор или выбрать более мощный алгоритм синтаксического анализа, такой как LR (1).   -  person rici    schedule 21.10.2016
comment
@rici У меня есть еще один вопрос, не могли бы вы ответить на него. Является ли моя грамматика LL(K)? Соответствует ли грамматика LL(K) грамматике LL(1)? Какое-то время меня смущало, что LL1() принадлежит к подмножеству для LL(K)   -  person Jebathon    schedule 21.10.2016
comment
это LL(2), потому что вы можете принять решение на основе следующих (2) токенов. Да, LL(k) является подмножеством LL(k'), если k ‹= k'.   -  person rici    schedule 21.10.2016

Ответы (1)


arrow_upward
0
arrow_downward

Приведенная выше грамматика на самом деле не является LL(k) для любого k, но мы можем построить LL(1)-грамматику для того же языка:

start -> statement // cannot change

statement -> IDENTIFIER statement0 SEMICOLON

statement0 ->  EQUAL expression

statement0 ->  LPAREN parameters RPAREN SEMICOLON

Конечно, в описании задачи мы не видим определение выражения и параметров, поэтому предполагаем, что можем построить и для них правила LL(1) (что не гарантируется, пока мы не увидим правила).

person Slava    schedule 03.11.2016