Pull to refresh

Работа с генератором трансляторов coco/r

Reading time 7 min
Views 12K
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+*:=
Tags:
Hubs:
+14
Comments 4
Comments Comments 4

Articles