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

Е.С.Борисов

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

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

Алфавит - конечное множество A из элементов, которые называют символами.
Слово (цепочка) в алфавите A - конечная последовательность символов из A. Пустое слово - последовательность, не содержащая ни одного символа (обозн. $\varepsilon$ ).
Язык в алфавите A - множество слов в A.
Язык можно задать с помощью грамматики.
Грамматика [1] :

G=(T,N,P,s)

где :
- T - алфавит терминальных символов
- N - алфавит нетерминальных символов (вспомогательные символы, синтаксические переменные или понятия), N U T = V - словарь грамматики G ; $N\cap T=\oslash$ ;
- P - продукции - конечное множество правил вывода,
  вида: $n\to w$ , где $n\in \bigcup\limits_{n \geq 1}( V^n )$ , $w \in \bigcup\limits_{n \geq 0}( V^n )$
- $s\in N$ - начальный нетерминал
Грамматику называют контекстно-свободной (КС) [2]
если ее продукции имеют вид $n\to w$ , где $n\in N$ , $w \in \bigcup\limits_{n \geq 0}( V^n )$
Контекстно-свободный язык (КСЯ) - язык, порождённый КС грамматикой
Слово $\eta$ непосредственно выводимо из слова $\sigma$ в грамматике G тогда и только тогда,
когда $\exists$ слова $\alpha,\beta,v$ , нетерминал n и правило вывода $n\to v$
такие, что $\sigma=\alpha n\beta$ , $\eta=\alpha v\beta$
обозн. $\sigma\Rightarrow\eta$
Слово $\alpha_n$ выводимо из слова $\alpha_0$ в грамматике G
если $\alpha_n=\alpha_0$ или $\exists$ последовательность слов $\{\alpha_0 , \alpha_1 , \ldots , \alpha_{n-1} , \alpha_n\}$ , такие, что $\alpha_{i-1}\Rightarrow\alpha_i$
обозн. $\alpha_0\stackrel{*}{\Longrightarrow}\alpha_n$
Язык L(G), порождённый грамматикой G - множество слов w, состоящих из терминальных символов T, выводимых из начального нетерминала s

$\begin{displaymath}L(G)=\{ w\ \vert\ s \stackrel{*}{\Longrightarrow} w\ ;\ w\in \bigcup\limits_{n \geq 0}( T^n ) \}\end{displaymath}$
Задача анализа :
заданы грамматика G и некоторое слово w.
Определить - верно ли, что $w\in L(G)$ ?
Алгоритмы анализа слева направо - рассматриваем символы слова w слева направо.
Стратегии анализа :
- сверху вниз - построить вывод от начального нетерминала s к заданному слову w.
- снизу вверх - вывод в обратном порядке, из заданного слова w получить начальный нетерминал s.

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-спецификация состоит из трёх секций, разделённых %%:

   определения
   %%
   правила
   %%
   подпрограммы

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

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

шаблоны описываются с помощью нотации, называемой регулярными выражениями[4]. Простейшие регулярные выражения это цепочки из букв.
действие это программа на языке C

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-спецификация, состоит из трёх секций, разделённых %%:

   определения
   %%
   продукции
   %%
   подпрограммы

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

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

имя - нетерминальный символ
цепочка - последовательность (возможно пустая) из имён и лексем. Она может включать в себя действия т.е. программы на C.

Продукции с одинаковой левой частью можно записывать вместе:
<имя>: <цепочка 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

При использовании материалов этого сайта, пожалуйста вставляйте в свой текст ссылку на мою статью.