YACC – Yet Another Compiler Compiler
Определение 1. Пусть A – некоторый алфавит, то есть произвольное непустое множество. Элементы этого множества будем называть символами. Произвольная конечная последовательность символов алфавита (в том числе и пустая) называется цепочкой. Произвольное подмножество LA множества всех возможных цепочек называется языком над A.
Пример 1. Язык LA правильных математических формул над алфавитом A, состоящим из 26 строчных латинских букв, двух скобок и четырех знаков арифметических действий (+, -, * /). Например, (a+b)*c
Определение 2. Пусть A – некоторый алфавит, M – метаалфавит, то есть какой-то другой алфавит, не пересекающийся с A. Элементы метаалфавита M называются метасимволами. Грамматикой называется система правил (то есть конечная последовательность строк) вида:
α → цепочка над (M ∪ A),
где α ∈ M – какой-то метасимвол, в который для каждого α ∈ M встречается хотя бы одна строка с α в левой части (до стрелочки) и в которой выделен один метасимвол, называемый главным.
Пример 2. Пусть A – алфавит из примера 1, M = {α,β,γ}, α — главный метасимвол, а грамматика такова:
α → ( α)
α → β
α → α γ α
β → a
β → b
…
β → z
γ → +
γ → -
γ → *
γ → /
Каждое правило грамматики имеет смысл подстановки. Например, строка “α → α γ α» означает возможность замены метасимвола α на цепочку α γ α.
Начав с главного метасимвола и пользуясь различными правилами грамматики, мы можем получать различные цепочки, состоящие из символов и метасимволов.
Например, цепочку (x+y) можно получить так:
1 3 2 2 30 27 28
α → (α) → (α γ α) → (α γ β) → (β γ β) → (β + β) → (x + β) → (x + y)
А цепочку, состоящую из единственного символа z, можно получить так:
2 29
α → β → z
Такие последовательности подстановок можно записать в виде дерева вывода, или дерева разбора:
--α--
| | |
(-α-)
|| | ||
(α γ α)
|| | ||
(β + β)
|| | ||
(x + y)
Если в цепочке встречается метасимвол, то его можно преобразовать дальше, применив одно из правил грамматики с этим метасимволом в левой части.
Если же метасимволов в цепочке не осталось, то процесс ее преобразования закончен и больше с цепочкой ничего сделать нельзя.
По этой причине обычные символы называются терминалами («конечными» символами), а метасимволы — нетерминалами.
Определение. Все множество цепочек над A (то есть цепочек без метасимволов), которые можно получить таким образом, называется языком, порожденным данной грамматикой, или языком, заданным с помощью данной грамматики.
Метасимволы (нетерминалы) обычно имеют некоторый смысл.
Так, в приведенной в примере 2 грамматике символ α означает правильную формулу, β - имя переменной, а γ - знак операции.
В таком случае для обозначения метасимволов часто используются сами понятия, взятые в угловые скобки. Например, <формула>, <имя переменной>, <знак операции>. Грамматика при этом примет вид:
<формула> → (<формула>)
<формула> → <имя переменной>
<формула> → <формула><знак операции><формула>
Кроме этого, правила грамматики с одинаковой левой частью объединяют, используя вместо стрелочки знак ::= (читается «это есть») и разделяя варианты вертикальной чертой (читается «либо»):
<формула> ::= <формула> | <имя переменнной> | <формула><знак операции><формула>
<имя переменной> ::= a | b | c | d | … | z
<знак операции> ::= + | - | * | /
Такую запись правил грамматики называют нормальной формой Бэкуса-Наура или сокращенно НФБН.
Программа YACC (Yet Another Compiler Compiler) предназначена для построения синтаксических анализаторов контекстно-свободного языка. Анализируемый язык описывается с помощью грамматики в виде, близком форме Бэкуса-Наура (НФБН). Результатом работы YACC является программа на языке C, реализующая восходящий LARL(1) распознаватель.
Структура YACC программы
YACC-программа состоит из трех секций, разделенных символами %% - секции описаний, секции правил, в которой описывается грамматика, и секции программ, содержимое которой просто копируется в выходной файл.
Секция описаний содержит информацию о том, какие символы являются лексемами (заданы с ключевым словом %token), и порядок выполнения операций (выполнять ли их слева направо или справа налево).
Файл, порождаемый YACC, содержит таблицы LARL(1) анализатора и C-текст функции yyparse(void), реализующей интерпретатор таблиц и семантические действия. Для запуска парсера надо вызвать эту функцию, она в случаае успешного разбора возвращает 0, в случае ошибки 1.
Для получения очередной лексемы парсер вызывает функцию int yylex(void). Она должна возвратить код лексемы и поместить ее значение в переменную YYSTYPE yylval.
Код лексемы — это положительное целое число.
Для доступа к значению терминала или нетерминала используются псевдопеременные $$ (значение левого символа правила) и $i (значение i-ого символа правой части правила).
Пример 3. Программа на языке YACC, вычисляющая значение арифметического выражения (вариант для дисплейного класса).
====================================================================
%{
#include
<stdio.h>
#include <ctype.h>
%}
%token
NAME
%left '+' '-'
%left '*' '/'
%%
s : e {
printf("%d\n", $1); }
e : e '+' e { $$ = $1 + $3; }
|
e '-' e { $$ = $1 - $3; }
| e '*' e { $$ = $1 * $3; }
| e
'/' e { $$ = $1 / $3; }
| '(' e ')' { $$ = $2; }
| NAME
;
%%
int yylex() {
register int c, v;
while
((c=getchar()) == ' ');
if (isdigit(c)) {
for( v=c-'0';
isdigit( c=getchar() ); ) v = v * 10 + c - '0';
ungetc( c, stdin
);
yylval = v;
return( NAME );
} else if ( c == '\n' )
{
return 0;
} else {
yylval = c;
return
yylval=c;
}
}
int main() { for(;;) yyparse();
return 0; }
int yyerror(char *mes) { printf( "%s\n",
mes ); return 0; }
====================================================================
В ОС Линукс трансляция этой программы в программу на языке C осуществляется следующей командой:
$ yacc CalcExpr.y
Результатом работы YACC является программа на языке С в файле y.tab.c, которая может быть скомпилирована при помощи компилятора gcc и выполнена.
$ gcc y.tab.c
Входными данными для этой программы является строка, представляющая собой арифметическое выражение, а выходными — значение этого выражения:
$ ./a.exe
8-(2+3)*2
-2
2-7*5
-33
1. Кушниренко А.Г., Лебедев Г.В. Программирование для математиков: Учеб. пособие для вузов — М.: Наука. Гл.ред.физ.-мат.лит., 1988, с.150-166