Преобразование грамматики в грамматику LL (1): некоторые проблемы - PullRequest
Новая
       43

Преобразование грамматики в грамматику LL (1): некоторые проблемы

5 голосов
/ 31 марта 2012

Это не совсем домашнее задание, но оно связано с моей учебой:

Например, грамматика выглядит так:

E -> E + E | E * E | -E | (E) | id

После устранения неоднозначности становится (начиная с оператора с наименьшим приоритетом) 

E->-F|F
F->F+G|G
G->G*H|H
H->(E)|id

И после удаления левой рекурсии и левого факторинга (в данном случае не требуется) окончательная грамматика LL1 будет: 

E->-F|F
F->GF'
F'->+GF'|e
G->HG'
B->*HG'|e
H->(E)|id

Что дает безошибочную таблицу парсера, которая работает нормально. Теперь о проблеме, с которой я сталкиваюсь, предположим, что грамматика такая:

E -> E + E | E * E | id = E | (E) | id

Теперь я не могу создать таблицу синтаксического анализа без конфликтов, что означает, что моя последняя грамматика не LL1. Вот шаги:

после устранения неоднозначности: 

E->id=F|F
F->F+G|G
G->G*H|H
H->(E)|id

А после удаления левой рекурсии и левого факторинга, грамматика становится: 

E->id=F|F
F->GF'
F'->+GF'|e
G->HG'
B->*HG'|e
H->(E)|id

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

1 Ответ

2 голосов
/ 31 марта 2012

Допустим, что: 

E -> E+E|E*E|id=E|(E)|id

станет: 

E -> E+E|E*E|(E)|E'
E' -> id=E|id

тогда вы можете убрать неопределенность и левую рекурсию и получить: 

E -> GF       FIRST(E) = FIRST(G)
F -> +GF|e
G -> HG'      FIRST(G) = FIRST(H)
G' -> *HG'|e
H -> (E)|E'   FIRST(H) = {(} + FIRST(E') = {(, id} 
E' -> idE''   FIRST(E') = {id}
E'' -> =E|e   FIRST(E'') = {=} + {#}

Конечно, проблема в том, что вы теряете заданный приоритет оператора.

Грамматика не будет LL (1), если для любого нетерминала N, будет любых общих элементов в FIRST(N -> a) и FIRST(N -> b) для N -> a, N -> b отличающиеся от N.

Как видите, добавление производства N -> id= в в любом другом месте нарушило бы это правило .

Вы можете создать грамматику LL(2) (но это, вероятно, не то, что вам нужно), которая может производить id=E в любом месте. (FIRST2 наборы состоят из 2-элементных строк).

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

E -> E+E|E*E|id=E|(E)|id

Весьма вероятно, что приоритет оператора, который я сделал в приведенном выше решении, является правильным для реального применения. Проверьте это!

...