Теория синтаксического анализатора

#синтаксический_анализ #лексический_анализатор

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

Следующим шагом должно быть разбиение лексем на классы (мне нужно отличить идентификаторы
в паскале).

Как отличить идентификаторы от не идентификаторов?
Выполнять проверку на на принадлежность к определенной множеству зарезервированных
слов (операторов и т д)?

При разбиении на классы нужно использовать дерево. Как я не понимаю.
На первом уровне должны быть типы лексем?
Каждым элементом кроны должен быть определенная лексема, которая встречается в коде?

Помогите, пожалуйста, разобраться.
    

Ответы

Ответ 1

Классификация лексем зависит, конечно, от языка.
Для начала, идентификаторы паскаля начинаются с буквы, поэтому вы их никак не спутаете
с операторами.
Конкретно для паскаля есть фиксированный набор идентификаторов, которые опознаются
как ключевые слова. Так что получив идентификатор, просто проверяйте, нет ли его в списке.

Рискну предположить, что под "деревом" для классификации лексем подразумевается следующая
конструкция:
Лексема -- это либо идентификатор (начинается с буквы и содержит буквы, цифры и знак
подчёркивания), либо скобка, либо оператор, либо знак пунктуации.
Идентификатор -- это либо ключевое слово (список прилагается), либо имя.
Скобка -- это либо круглая скобка, либо квадратная (фигурные выбросил препроцессор),
может быть открывающей и закрывающей.
Оператор -- это один из списка (плюс, минус, ...)
И так далее. Видите дерево?


Ответ 2

Самый простой способ получить пару лексический/синтаксический анализатор на практике
сгенерировать его автогенератором из БНФ грамматики языка с помошью Flex и Bison (lex
и yacc). Если хотите написать самому нормальный парсер курите теорию конечных автоматов
и формальных языков. Если пытаться интутивно писать его, то с вероятностью 99% после
первой попытки получится медленная, плохо-читаемая конструкция состоящая из условных
переходов и сравнений строк чуть менее чем полностью. При этом сама эта конструкция
на самом деле будет являться кривой реализацией конечного автомата для данной грамматики,
но написавший её может даже  и не подозревать что это так. 
Вот пример уже готовой lex и yacc грамматики для Паскаля. Всего 1000 строк кода. 

scanner.l;
parser.y;

P.S. Если захотите скомпилировать эту грамматику под Windows стоит брать flex.exe
bison.exe из Cygwin или MinGW, а не с сайта GNU там почему-то лежат старые версии.