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

Тема в разделе "LANGS.C", создана пользователем VaVa, 21 фев 2019.

  1. VaVa

    VaVa Member

    Публикаций:
    0
    Регистрация:
    21 авг 2018
    Сообщения:
    34
    смотрю страницу на википедии не могу ничего понять про принцип и даже про задание условия в примере
    Как я понимаю таблица строится из грамматики, но откуда взялась такая грамматика
    1. S → F
    2. S → (S + F)
    3. F → 1
    В регулярных выражениях понятнее там язык соответствует тому что мы хотим найти
    а тут что означает грамматика не понятно.
     
  2. Pavia

    Pavia Well-Known Member

    Публикаций:
    0
    Регистрация:
    17 июн 2003
    Сообщения:
    2.409
    Адрес:
    Fryazino
    VaVa, забейте на это в википеди написана откровенная чушь. Автор путает порождающие цепочки, с грамматикой. Да ещё парсер с генератором.
     
    Mikl___ и TermoSINteZ нравится это.
  3. VaVa

    VaVa Member

    Публикаций:
    0
    Регистрация:
    21 авг 2018
    Сообщения:
    34
    а можно ещё где нибудь прочитать на русском про алгоритмы на которых основан Yacc Bison?
     
  4. gazlan

    gazlan Member

    Публикаций:
    0
    Регистрация:
    22 май 2005
    Сообщения:
    414
  5. Pavia

    Pavia Well-Known Member

    Публикаций:
    0
    Регистрация:
    17 июн 2003
    Сообщения:
    2.409
    Адрес:
    Fryazino
    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 то стек заменяете очередью и правила проверяются не на вершине стека а в конце очереди.

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