на главную ] 

Методы и средства построения грамматических анализаторов.

Е.С.Борисов

суббота, 29 ноября 2003 г.


1 Введение в теорию формальных языков

 

 
 

2 Средства лексического и синтаксического анализа.

Задачу построения грамматического анализатора можно разделить на две подзадачи - построение лексического (ЛА) и синтаксического (СА) анализаторов.

Рисунок: схема грамматического анализатора
\begin{figure}\centering {\tt текст $\stackrel{ЛА}{\longrightarrow}$лексемы $\stackrel{СА}{\longrightarrow}$результаты анализа}
\end{figure}

Для построения грамматического анализатора можно использовать пару утилит - lex и yacc. Обычно, эти утилиты входят в стандартный набор UNIX/Linux систем. В Internet доступны их реализации почти для всех OS (MS Windows etc.).

2.1 Лексический анализатор

Лексический анализатор (сканер) читает входной поток, выделяет терминальные символы т.е. элементарные конструкции или лексемы, и передаёт их процедуре синтаксического разбора. Для реализации лексического анализатора будем использовать утилиту lex.

Рисунок: схема работы lex
\begin{figure}\centering {\tt спецификация $\stackrel{lex}{\longrightarrow}$ исходник ЛА на языке C $\stackrel{cc}{\longrightarrow}$ программа ЛА}
\end{figure}

lex-спецификация состоит из трёх секций, разделённых %%:

   определения
   %%
   правила
   %%
   подпрограммы
Обязательной является только секция правил. Секции определений и подпрограмм могут отсутствовать.

Правила имеют вид : <шаблон> <действие>

2.2 Синтаксический анализатор

Синтаксический анализатор - проверяет цепочки лексем, полученные от лексического анализатора, на соответствие данной грамматике. Для реализации синтаксического анализатора будем использовать утилиту yacc. Обычно, yacc-синтаксический анализатор строится с использованием lex-сканера, но это не обязательно - лексический анализатор для yacc можно построить и другим способом, например - написать его самостоятельно.

yacc, по спецификации, описывающей грамматику в форме близкой к Бэкусово-Науровской (БНФ)[1], строит LR(1) анализатор [2] (стратегия снизу вверх).

Рисунок: схема работы yacc
\begin{figure}\centering {\tt спецификация $\stackrel{yacc}{\longrightarrow}$исходник CА на языке C $\stackrel{cc}{\longrightarrow}$программа CА}
\end{figure}

yacc-спецификация, также как и lex-спецификация, состоит из трёх секций, разделённых %%:

   определения
   %%
   продукции
   %%
   подпрограммы
Обязательной является только секция продукций. Секции определений и подпрограмм могут отсутствовать.

Продукции имеют вид : <имя>: <цепочка> ;

Продукции с одинаковой левой частью можно записывать вместе:
<имя>: <цепочка 1> | <цепочка 2> | ... ;

 

 
 

3 Пример

В данном примере построен простой калькулятор над целыми числами, с четырьмя операциями.

[ лексический анализатор ] [ синтаксический анализатор ] [ исходники ( 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
 

 
 

Литература

1
Д.Кук, Г.Бейз Компьютерная математика - Москва: Наука, 1990 - 384 стр.

2
А.Ахо, Дж.Ульман Теория синтаксического анализа, перевода и компиляции - Москва: МИР, 1978

3
В.С.Проценко, П.Й.Чаленко Элементы компиляции - Киев: УМК ВО, 1988 - 55 стр.

4
UNIX manual pages - man re_format

Evgeny S. Borisov
2003-11-29
Яндекс.Метрика
TOP.zp.ua PR-CY.ru
При использовании материалов этого сайта, пожалуйста вставляйте в свой текст ссылку на мою статью.