Использование LR(1) автомата для синтаксического разбора файла
Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті
Для создания вашего любимого языка программирования наверняка использовались специальные программы, которые генерируют несколько автоматов, которые по заданной программе производят сперва лексический, а затем синтаксический разбор исходного текста программы. Обычно используется LALR(1) автоматы. Один автомат выделяет лексемы, а второй автомат на основе полученных лексем производит синтаксический разбор. Для генерации лексического анализатора обычно используют программу flex, а для генерации синтаксического анализатора программу bison. Обе программы генерируют LALR(1) автоматы.
Сама теория синтаксического анализа чертовски сложная штука и понять ее далеко не каждому математику под силу. Поэтому приводить всякие заумные изречения я не буду. Желающие могут сами все найти в сети.
В то время, когда производительность компьютеров была не очень высокой и ценился каждый байт оперативной памяти, разработчики из множества методов анализа выбрали LALR(1). Он был достаточно мощным и имел малое количество состояний. Другие более сложные методы были отвергнуты хотя были намного мощнее, т.е. могли производить разбор более сложной грамматики. Тот же LR(1) метод имеет примерно в десять раз больше состояний, чем LALR(1). Но и преимущество налицо. Он с легкостью производит синтаксический разбор грамматики, в которой переменные могут состоять из нескольких отдельных слов не путая их с ключевыми словами.
Так как на данный момент проблема производительности или нехватки памяти не стоит, то было решено попробовать реализовать LR(1) автомат. Была разработана программа, которая производит разбор mtl файлов. Это файлы, в которых хранятся свойства материалов для трехмерной модели. Программа состоит из двух LR(1) автоматов, один из которых производит лексический, а другой синтаксический анализ файлов.
Ниже приводится полностью грамматика лексического анализатора и кусочек грамматики синтаксического анализатора.
s: s: tokens tokens: token tokens: tokens token token: number number: intNumber number: floatNumber intNumber: NUMBER intNumber: intNumber NUMBER floatNumber: intNumber . intNumber token: word word: LETTER word: word LETTER word: word NUMBER word: word _ word: word . token: space space: WHITESPACE space: space WHITESPACE token: EOL token: EOF token: key key: - LETTER key: key LETTER token: comment comment: # comment: comment {NO_EOL}
Терминалы для вышеприведенной грамматики:
- . _ NUMBER LETTER EOL EOF WHITESPACE {NO_EOL} #
s s: lines lines: line lines: lines line line: EOL line: command EOL line: command EOF line: error EOL line: error EOF command: newmtl command: ka newmtl: NEWMTL file file: WORD file: command ka: KA NUMBER NUMBER NUMBER ka: KA NUMBER ka: KA SPECTRAL WORD NUMBER ka: KA SPECTRAL WORD ka: KA XYZ NUMBER NUMBER NUMBER ka: KA XYZ NUMBER
Терминалы для вышеприведенной грамматики:
NUMBER KA SPECTRAL WORD XYZ EOL EOF NEWMTL
Причем LR(1) автоматы не классические, а немного измененные.
Программа была написана на javascript. Используя данное программное обеспечение можно даже написать компилятор языка си, который будет работать в браузере. Конечно, это будет очень медленно работать, но будет.
1 коментар
Додати коментар Підписатись на коментаріВідписатись від коментарів