LL-анализатор

смотрю страницу на википедии не могу ничего понять про принцип и даже про задание условия в примере
Как я понимаю таблица строится из грамматики, но откуда взялась такая грамматика

1. S → F
2. S → (S + F)
3. F → 1

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

 

VaVa, забейте на это в википеди написана откровенная чушь. Автор путает порождающие цепочки, с грамматикой. Да ещё парсер с генератором.

 

а можно ещё где нибудь прочитать на русском про алгоритмы на которых основан Yacc Bison?

 

Посмотрите Теория программирования на Куличиках. По этим авторам и ищите.

 

VaVa, По теории хорошо пишет:
Карпов Ю.Г._основы построения трансляторов
Книга лежит в колхозе и в генезисе.
Ещё одна книга это Опалева Э.А., Самойленко В.П. -Языки программирования и методы трансляции-БХВ (2005)
Тут особо вам будет интересна 6 глава.

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

Код (Pascal):

1. // Кастуем лексему в узел.
2. Node.IsTerminal:=True;
3. Node.Lexem:=curLexem;
4. Node.Name:=curLexem;
5.  

Заносим в стек

Код (Pascal):

1. // сдвиг.
2. Stack.Push(Node);
3.  

Проверяем все правила перебором.
Если какое либо правило совпало, то выполняем свёртку.
Заменяем группу узлов на новый.

Код (Pascal):

1. // Свёртка.
2. NewNode:=TNode.Create;
3. NewNode.IsTerminal:=False; // не терминальный символ
4. NewNode.Name:=Rule.Name;
5. For i:=0 to Rule.Length-1 do
6.   NewNode.Add(Stack.Pop)
7. Stack.Push(NewNode);
8.  
9. //Обработка
10. Rule.OnFunction(NewNode) - // вызываем функцию из сгенерированого кода.
11.  

И так до тех пор пока стек не опустеет либо лексемы не закончатся.

Тут свёртка для анализа вида RR, если надо LL то стек заменяете очередью и правила проверяются не на вершине стека а в конце очереди.

Плюс у бизона в правила добавлены приоритеты операторов. Там свёртка выполняется над группой узлов когда на вершине стека окажется оператор с низшим приоритетом.