Е.С.Борисов
суббота, 29 ноября 2003 г.
где :
Задачу построения грамматического анализатора можно разделить на две подзадачи - построение лексического (ЛА) и синтаксического (СА) анализаторов.
Для построения грамматического анализатора можно использовать пару утилит - lex и yacc . Обычно, эти утилиты входят в стандартный набор UNIX/Linux систем. В Internet доступны их реализации почти для всех OS (MS Windows etc.).
Лексический анализатор (сканер) читает входной поток, выделяет терминальные символы т.е. элементарные конструкции или лексемы , и передаёт их процедуре синтаксического разбора. Для реализации лексического анализатора будем использовать утилиту lex .
lex-спецификация состоит из трёх секций, разделённых %% :
определения %% правила %% подпрограммыОбязательной является только секция правил. Секции определений и подпрограмм могут отсутствовать.
Правила имеют вид : <шаблон> <действие>
Синтаксический анализатор - проверяет цепочки лексем, полученные от лексического анализатора, на соответствие данной грамматике. Для реализации синтаксического анализатора будем использовать утилиту yacc . Обычно, yacc-синтаксический анализатор строится с использованием lex-сканера, но это не обязательно - лексический анализатор для yacc можно построить и другим способом, например - написать его самостоятельно.
yacc , по спецификации, описывающей грамматику в форме близкой к Бэкусово-Науровской (БНФ)[ 1 ], строит LR(1) анализатор [ 2 ] (стратегия снизу вверх).
yacc-спецификация, также как и lex-спецификация, состоит из трёх секций, разделённых %% :
определения %% продукции %% подпрограммыОбязательной является только секция продукций. Секции определений и подпрограмм могут отсутствовать.
Продукции имеют вид : <имя>: <цепочка> ;
В данном примере построен простой калькулятор над целыми числами, с четырьмя операциями.
[
лексический анализатор
]
[
синтаксический анализатор
]
[
исходники ( tar+gzip )
]
[ calculator ]$ make yacc -d calculator.y lex calculator.l cc y.tab.c lex.yy.c -ly -ll -o calculator [ calculator ]$ make run echo '(4+6)*55+(34-21+1)/2+3' | ./calculator 560