Объяснить Разбор таблицы в http://hackingoff.com/compilers/ll-1-parser-generator

Question

Я использую следующую грамматику в http://hackingoff.com/compilers/ll-1-parser-generator:

E -> T E' 
E' -> + T E' 
E' -> EPSILON 
T -> F T' 
T' -> * F T' 
T' -> EPSILON 
F -> (E) 
F -> id 

Выходной Синтаксический Таблица является

[ 
     [0, "+", "*", "(", ")", "id", "$"], 
     [0, 0, 0, 0, 0, 0, 0], 
     [0, 10, 10, 1, 9, 1, 9], 
     [0, 2, 10, 10, 3, 10, 3], 
     [0, 9, 10, 4, 9, 4, 9], 
     [0, 6, 5, 10, 6, 10, 6], 
     [0, 9, 9, 7, 9, 8, 9] 
] 

Может ли кто-нибудь объяснить парсинг? В частности, то, что смысл 9 и 10, учитывая, что есть только 8 линий в правилах производства

Answer 1

Это объясняется в самой странице, прямо над столом:

Если терминал отсутствует набор прогнозов, не относящихся к терминалу, в таблицу помещается код ошибки. Если этот терминал находится в состоянии (что не является терминалом), ошибка является ошибкой POP. Иначе, это ошибка SCAN.

POP код ошибки = # из предсказать таблица производства + 1

SCAN код ошибки = # из предсказать таблица производства + 2

Таким образом, в случае грамматики с восьми правил производства, значения 9 и 10 - POP error и SCAN error, соответственно.

Answer 2

Я также пробовал использовать очень простую грамматику на сайте hackingoff.com, но я немного запутался в результатах.

Грамматика я использовал следующее:

1. E -> int T 
2. T -> + int 
3. T -> ε 

Я сделал некоторые ручной расчет и разработаны следующие:

First(int) = {int} 
First(+) = {+} 
First(ε) = {ε} 
First(E) = {int} 
First(T) = {+,ε} 

Follow(E) ⊆ Follow(T) 
First(T) ⊆ Follow(int) 
Follow(E) ⊆ Follow(int) 
First(int) ⊆ Follow(+) 
Follow(E) ⊆ Follow(int) 

=> 

Follow(E) = {$} 
Follow(T) = {$} 
Follow(int) = {+,$} 
Follow(+) = {int} 

Тогда я построил парсинга таблицу:

int  +  $ 
    ------------------------ 
E | int T    | 
T |   +int  ε | 
    ------------------------ 

Но когда я использую эту грамматику на сайте hackingoff.com, она говорит - от того, что я хочу rstand - что грамматика имеет некоторые ошибки. В таблице, которая отображается на сайте следующее:

[0,"int","+","$"] 
[0,0,0,0] 
[0,1,5,4] 
[0,5,2,3] 

Из того, что я понял из описания на сайте есть ошибки, когда - в моем случае - значение в ячейке таблицы больше 3 Очевидно, проблема в ячейках без какой-либо продукции в моей таблице. Когда я вручную построил таблицу синтаксического анализа там, где нет столкновений в ячейке, так почему это дает мне ошибки? Наверное, я пропустил что-то фундаментальное?

parsingcontext-free-grammar