coco/r генератор компиляторов и трансляторов, который по атрибутной грамматике генерирует сканер (лексический анализатор) и парсер (синтаксичсекий анализатор). Сканер строится как детерминированный конечный автомат, а парсер — рекурсивным спуском.
1. Грамматика
Генератор формирует код по РБНФ правилам. Т.к. Парсер стоится рекурсивным спуском, а это разбор сверху-вниз, то грамматика должна принадлежать LL(k). В идеале LL(1), но в coco/r сделано разрешение конфликтов.
LL(1) конфликты решаются за счет семантических действий и просмотра впереди стоящих лексем.
Грамматика является LL(1), если для двух различных продукций S->A|B выполняются условия:
1. Не существует такого терминала а, для которого А и В порождают строку, начинающуюся с а.
2. Пустую строку может порождать не более чем одна из продукций А или В.
3. Если е принадлежит множеству FIRST(B), то множества FIRST(A) FOLLOW(S) — не пересекаются. Аналогичное утверждение для е, принадлежащего FIRST(A), тоже верно.
2. Язык coco/r
Генератор может создавать код на языках: java, C++, C#, F#, VB.Net, Oberon.
В примере был взят С++.
Все правила должны заканчиваться точкой.
Продукция вида S->AB будет записана как S=A B.
| — или
( ) — группа
[ ] — 0 или 1
{ } — 0 или более
2.1 Импорт, т.е. подключение хидеров.
#include <string>
#include <sstream>
#include <iostream>
#include <fstream>
#include <vector>
2.2 Идентификатор компилятора, т.е. далее следует ключевое слово COMPILER, а за ним нетерминал, с которого начинается ваша грамматика.
COMPILER expr
2.3 Глобальные переменные и функции.
После ключевого слова COMPILER можно вставить секцию с переменными и функциями. Если функций много, то лучше их вынести в отдельный файл, т.к. грамматика и без них получится очень страшной и нечитабельной.
int toInt(const std::wstring& strbuf)
{
std::wstringstream converter;
int value = 0;
converter << strbuf;
converter >> value;
return value;
}
std::wstring toString ( int Number )
{
std::wostringstream ss;
ss << Number;
return ss.str();
}
2.4 Правила для генерации сканера.
2.4.1 IGNORECASE ключевое слово для игнорирования регистра символов.
2.4.2 CHARACTERS — секция, в которой мы описываем множество допустимых символов. Например, что такое для нас буква и что такое цифра.
CHARACTERS
letter = «ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz».
digit = «0123456789».
Так же здесь можно описать символы-разделители.
cr = 'r'.
lf = 'n'.
tab = 't'.
Запись вида char 1.. char2 обозначает последовательность символов от char1 до char2.
digit = '0'..'9'.
ANY — любая последовательность символов.
+ включая множество
— не включая
Например, можно описать множество символов, в которое не входят двойные кавычки:
verbatimStringChar = ANY — '"'.
Множество символов для шестнадцатеричной системы счисления:
hexDigit = digit + «ABCDEFabcdef».
2.4.3 Сами токены, или еще одно название — лексемы. Ключевое слово раздела — TOKENS. Описываем, что мы понимаем под лексемой «идентификатор» и лексемой «число».
TOKENS
ident = letter {letter | digit | "_"}.
number = digit {digit}.
Лексема «строка», как любая последовательность символов, заключенная в двойные кавычки:
string = """ {verbatimStringChar} """.
Число из шестнадцатеричной системы счисления:
hex = «0x» {hexDigit hexDigit}.
2.4.4 Секция специальных опций.
2.4.5 Комментарии.
COMMENTS FROM "/*" TO "*/" NESTED
COMMENTS FROM "//" TO cr lf
2.4.6 Разделители. Пишем, какие разделители мы игнорируем.
IGNORE cr + lf + tab
2.5 Правила для генерации парсера.
Начинаются с ключевого слова PRODUCTIONS.
Пример грамматики выражений:
Expr= ident ':=' NumExpr ';'
NumExpr = Term {('+'| '-' ) NumExpr}
Term = Multiplier {('*'| '/' )Term}
Multiplier = ident | number | '(' NumExpr ')'
Все атрибуты пишутся в скобках < >. Если вы что-то используете из stl, например, list, то атрибуты должны быть помещены в скобки с точками, т.е. <. .>.
Атрибуты пишутся у нетерминалов и транслируются как параметры функций.
У терминала нет атрибутов, но если так сильно хочется, то его можно обернуть в нетерминал:
LogOp<std::wstring &op>=("&&"|"||") (.op=t->val;.).
Семантические действия пишутся в скобках с точками (. .). Этот тот код, который генератор вставит в парсер. Код пишется на том языке, на котором генерируются лексер и парсер.
ANY -это ключевое слово в секции парсера обозначает любой токен. Так что мы можем описать «текст» как {ANY}.
2.6 Ключевое слово END, за которым следует имя, которое вы указали после COMPILER в 2.2.
3. Разрешение конфликтов.
Очень важно понимать, что грамматика должна соответствовать типу анализатора. Если это условие нарушено, то генератор начинает ругаться страшными словами.
3.1 Факторизация.
Правила начинаются с одного и того же токена. Генератор так и пишет several alternatives
Пример:
S->a '=' B | a '('C')'
Как видите, 2 правила начинаются с токена «а», что нарушает первое правило LL(1). Переписываем его как S-> a ('='B |'(' C ') ')
Некоторые конфликты, такие как if-else решить невозможно.
Statement = if '(' Eepr ')' Statement [else Statement].
if (a>b) if(a>c) max=a; else max=b;
Не ясно, что тут выбрать, поэтому было принято соглашение: выбирать первую альтернативу. В данном примере выбор правильный, но в своей грамматике лучше избегать таких неоднозначностей.
Неудачная запись.
S= a[id b] A.
A= id{.id}.
Не ясно какое правило выбрать, т.к. [id b] и A начинаются с одинаковых токенов. В таком случае лучше всего переписать грамматику:
S= a id ( b A| {. id}).
3.2 Левая рекурсия.
Левая рекурсия для LL грамматик никаким образом не допустима. Ее нужно удалить путем преобразования. К счастью любую левую рекурсию можно преобразовать в правую.
A->Aa1|...|Aan|b1...|bm
на
A->b1B|..|bmB
B->a1B|..|anB|e
Запись в РБНФ:
A = A b| c.
на
A = c {b}.
3.3 Семантическая значимость.
В некоторых случаях выбор правил производится исходя из их семантики. Например выражение с типами:
Expr=Factor { '+' Factor }.
Factor = '('ident')' Factor | '(' Expr ')' | ident| number.
Т.е. Такая грамматика допускает следующий цепочки:
a+b
(a)+b
(int)a+b
В последней цепочке выбор правила '('ident')' Factor обусловлен семантикой идентификатора. Т.е. Это правило выбирается, если у нас в качестве ident выступает тип.
! Крайне неудачный пример с точки зрения построения языка. Обычно в грамматике «ключевые слова» описываются отдельным правилом. Тогда нет необходимости в проверках идентификатора.
Другой пример.
A= ident (. x=1; .) {', ' ident (.x++;.) } ':' | ident (.Foo();.) {',' ident (.bar();.) } ';'.
В этом случае нельзя отредактировать грамматику, т. к. у одинаковых частей правила разные семантические действия. Чтобы определить правило, необходимо просмотреть все токены до двоеточия или точки с запятой. Только тогда станет ясно какое правило выбрать.
Решение:
В грамматику можно вставить булеву функцию, по которой будет выбрана альтернатива.
S= a[id b] A.
A= id{.id}.
S= a [ IF(isAlias()) id b] A.
IsAlias() функция, которая просматривает 2 впереди стоящих токена. Если это b, то возвращает true.
Token t -только что распознанный токен
Token la — следующий токен
t.val — значение токена
t.kind — тип токена, определяется лексером
A= IF (FollowedByColon())
ident (. x=1; .) {', ' ident (.x++;.) } ':'
| ident (.Foo();.) {', ' ident (. Bar();.) } ';'.
bool FollowedByColon(){
//берем следующий токен
Token x = la;
//пока текущий токен запятая или переменная
while(x.kind==_comma || x.kind== _ident)
//двигаем сканер на следующий токен
x=scanner.Peek();
//возвращаем true, если мы встретили двоеточие
return x.kind==_colon;
}
Примечания:
IF ключевое слово языка генератора.
Функция FollowedByColon() относится к первому правилу. Если она выдала true, то именно его она и рассматривает.
Имена типам токенов присваивает сканер. Но если в секции TOKENS сделать такие объявления
ident = letter {letter | digit | "_"}.
comma = ','.
semicolon = ';'.
colon = ':'.
То сканер сгенерирует константы с хорошими именами:
const int _EOF=0;
const int _ident=1;
const int _comma=2;
const int _semicolon=3;
const int _colon=4;
С точки зрения построения языка, отдельное описание каждого спец символа как токена не имеет смыла. Но если возникла потребность в написании условий, в которых требуется проверка впереди стоящих токенов, такое описание может быть полезно.
Если в первом правиле у вас была функция, в которой вы проверяли токены, а во втором правиле у вас тоже есть функция, то сканер должен вернуться в первоначальное положение. Сбросить позицию можно функцией scanner.ResetPeek().
4. Пример кода
Переведем выражение в постфиксную запись. Выражения должны выводится по вот такой грамматике:
Expr= ident ':=' NumExpr ';'
NumExpr = Term {('+'| '-' ) NumExpr}
Term = Multiplier {('*'| '/' )Term}
Multiplier = ident | number | '(' NumExpr ')'
файл atg:
#include <string>
#include <sstream>
#include <iostream>
#include <fstream>
#include <vector>
COMPILER expr
int toInt(const std::wstring& strbuf)
{
std::wstringstream converter;
int value = 0;
converter << strbuf;
converter >> value;
return value;
}
std::wstring toString ( int Number )
{
std::wostringstream ss;
ss << Number;
return ss.str();
}
IGNORECASE
CHARACTERS
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".
digit = "0123456789".
cr = 'r'.
lf = 'n'.
tab = 't'.
TOKENS
ident = letter {letter | digit | "_"}.
number = digit {digit}.
COMMENTS FROM "/*" TO "*/" NESTED
COMMENTS FROM "//" TO cr lf
IGNORE cr + lf + tab
PRODUCTIONS
expr (.std::wstring str;.) = (.std::wstring s,s1,s2,s3,s4; .)
ident (.s1=t->val;.)":=" NumExpr<s2> ";" (. str+=s1; str+=s2; str+=L":=n";.)
{ident(.s3=t->val; s4=L"";.)":=" NumExpr<s4> ";" (. s+=s3; s+=s4; s+=L":=n"; .)}
(.
str+=s;
std::wofstream outfile ("out.txt", std::ios_base::out);
outfile << str << std::endl;
outfile.close();
.)
.
NumExpr<std::wstring &str> = (.std::wstring s1,s2, op; .)
Term<s1> (.str+=s1;.)
{ ("+" (.op=L"+";.)|"-" (.op=L"-";.)) NumExpr<s2>
(. str+=s2; str+=op; .)
}.
Term<std::wstring &str> =(.std::wstring s1,s2, op;.)
Multiplier<s1> (.str+=s1;.)
{ ("*" (.op=L"*";.)|"/"(.op=L"/";.)) Term<s2>
(. str+=s2; str+=op; .)
}.
Multiplier<std::wstring &str> =
ident (.str=t->val; .)
| number (.str=t->val;.)
| (.std::wstring s; .) "(" NumExpr<s> ")" (.str=s;.).
END expr.
main:
#include <iostream>
#include <wchar.h>
#include "Parser.h"
#include "Scanner.h"
#include <string>
using namespace std;
main(int argc, char *argv[])
{
if (argc == 2)
{
wchar_t *file = coco_string_create(argv[1]);
Scanner *scanner = new Scanner(file);
Parser *parser = new Parser(scanner);
parser->Parse();
delete parser;
delete scanner;
delete file;
return 0;
}
else
{
cout << "Use: translator filename" << endl;
return 1;
}
}
make:
all: translator
translator: Coco scanner.o parser.o main.o
g++ -o tr.exe scanner.o parser.o main.o
main.o: main.cpp
g++ -c main.cpp
scanner.o: Scanner.cpp Scanner.h
g++ -c Scanner.cpp -o scanner.o
parser.o: Parser.cpp Parser.h
g++ -c Parser.cpp -o parser.o
Coco: expr.atg
coco expr.atg
clean:
del Scanner.cpp Scanner.h Parser.cpp Parser.h
del Scanner.cpp.old Scanner.h.old Parser.cpp.old Parser.h.old
del scanner.o parser.o main.o
del translator
Функция парсера, построенная по грамматике
void Parser::NumExpr(std::wstring &str) {
std::wstring s1,s2, op;
Term(s1);
str+=s1;
while (la->kind == 5 || la->kind == 6) {
if (la->kind == 5) {
Get();
op=L"+";
} else {
Get();
op=L"-";
}
NumExpr(s2);
str+=s2; str+=op;
}
}
вход
a:=b;
a:=a-5;
a:=9-5+2;
a:=2+3*4;
a:=(5-4)*(3+2);
выход
ab:=
aa5-:=
a952+-:=
a234*+:=
a54-32+*:=
Автор: awRabbit
