Конвертировать C-грамматику в LL(1)

Question

В настоящее время я создаю компилятор для C-. В настоящее время я работаю над синтаксическим анализатором, и по какой-то причине я не могу разрешить возникновение коллизии первых наборов (идентификатора терминала) из производства EXPRESSION. Ниже, является подмножеством грамматики, которую я имею сейчас, может кто-то указать мне правильное направление относительно того, как разрешить столкновение (или преобразовать в эквивалентную LL(1) разбираемую грамматику).

EXPRESSION ->   id VAR eq EXPRESSION |  SIMPLEEXPRESSION 

VAR ->  lbracket EXPRESSION rbracket |  empty

SIMPLEEXPRESSION -> ADDITIVEEXPRESSION FADDITIVEEXPRESSION 

FADDITIVEEXPRESSION ->  RELOP ADDITIVEEXPRESSION |  empty

RELOP ->    ltoreq |    lt |    gt |    gtoreq |    doubleeq |  noteq 

ADDITIVEEXPRESSION ->   TERM ADDITIVEEXPRESSION1 

ADDITIVEEXPRESSION1 ->  ADDOP TERM ADDITIVEEXPRESSION1 |    empty

ADDOP ->    plus |  minus 

TERM -> FACTOR TERM1 

TERM1 ->    MULOP FACTOR TERM1 |    empty

MULOP ->    times | divide 

FACTOR ->   lparen EXPRESSION rparen |  id FACTOR1 |    num 

FACTOR1 ->  a | b

Answer 1

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

Но для рассматриваемой проблемы, для производства на высшем уровне

EXPRESSION ->   id VAR eq EXPRESSION |  SIMPLEEXPRESSION 

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

Одним из решений насущной проблемы было бы разделение EXPRESSION производство на две альтернативы, одна, которая всегда начинается с id терминал, и тот, который никогда не делает:

EXPRESSION        ->   EXPRESSION_id |  EXPRESSION_non_id

Для id В качестве альтернативы нам потребуется id терминал впереди, а затем создать idтолько версии производств, которые следуют:

EXPRESSION_id     ->   id (VAR eq EXPRESSION |  SIMPLEEXPRESSION_id) 

Точно так же дляid сторона, мы бы создалиid версии производств, которые следуют:

EXPRESSION_non_id ->   SIMPLEEXPRESSION_non_id

Необходимые подпроизводства для завершения грамматики будут выглядеть примерно так:

SIMPLEEXPRESSION_id -> ADDITIVEEXPRESSION_id FADDITIVEEXPRESSION 
ADDITIVEEXPRESSION_id ->   TERM_id ADDITIVEEXPRESSION1 
TERM_id -> FACTOR_id TERM1
FACTOR_id ->   FACTOR1

SIMPLEEXPRESSION_non_id -> ADDITIVEEXPRESSION_non_id FADDITIVEEXPRESSION 
ADDITIVEEXPRESSION_non_id ->   TERM_non_id ADDITIVEEXPRESSION1
TERM_non_id -> FACTOR_non_id TERM1
FACTOR_non_id ->   lparen EXPRESSION rparen |  num

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