Сучасна диджитал-освіта для дітей — безоплатне заняття в GoITeens ×
Mazda CX 30
×

Использование 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. Используя данное программное обеспечение можно даже написать компилятор языка си, который будет работать в браузере. Конечно, это будет очень медленно работать, но будет.

👍ПодобаєтьсяСподобалось0
До обраногоВ обраному0
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Так как на данный момент проблема производительности или нехватки памяти не стоит

 Ну вот два примера из жизни:
1) Хромиуим компилится 40 минут на ноуте с SSD и час — с обычным диском
2) При запуске сборки прошивки для роуера, если открыты эклипс и браузер с почтами, линкедином и слаком — убунта уходит в трешинг.
То есть, обе проблемы живы (как минимум — для GCC) в разработке приложений, не говоря о корпоративных монолитах (энтерпрайз)

даже написать компилятор языка си

 Который — самый простой из ныне живых языков. Попробуйте лучше С++20.

Підписатись на коментарі