Создание синтаксического анализатора с помощью программы GPPG
Материал из Вики ИТ мехмата ЮФУ
Общие комментарии
- В данном проекте мы создадим front-end компилятор с помощью генератора парсеров gppg.
- Комплект для практического занятия скачиваем отсюда.
- Для автоматического создания парсера создаются файлы SimpleLex.lex (описание лексического анализатора) и SimpleYacc.y (описание синтаксического анализатора).
- Код лексического и синтаксического анализаторов создаются на C# запуском командного файла generateParserScanner.bat со следующим содержимым:
gplex.exe /unicode SimpleLex.lex gppg.exe /no-lines /gplex SimpleYacc.y
Параметр /gplex здесь означает, что gppg работает в связке с gplex.
Файл синтаксического анализатора SimpleYacc.y
%{
// Эти объявления добавляются в класс GPPGParser, представляющий собой парсер, генерируемый системой gppg
public Parser(AbstractScanner<int, LexLocation> scanner) : base(scanner) { }
%}
%output = SimpleYacc.cs
%namespace SimpleParser
%token BEGIN END CYCLE INUM RNUM ID ASSIGN SEMICOLON
%%
progr : block
;
stlist : statement
| stlist SEMICOLON statement
;
statement: assign
| block
| cycle
;
ident : ID
;
assign : ident ASSIGN expr
;
expr : ident
| INUM
;
block : BEGIN stlist END
;
cycle : CYCLE expr statement
;
%%Формат .y-файла
Определения %% Правила %% Пользовательский код
Комментарии к файлу SimpleYacc.y
- Файл синтаксического анализатора значительно проще и понятнее рукописного файла синтаксического анализатора. Он не содержит кода и содержит лишь спецификацию грамматики.
- Секция правил представляет собой описание грамматики языка. Пример правильной программы, удовлетворяющей этой грамматике:
begin
b := 2;
a := b;
cycle 3
begin
a := c;
c := 1
end
end
- Определение последовательности операторов - леворекурсивно:
stlist : statement
| stlist SEMICOLON statement
;В отличие от создания синтаксического анализатора методом рекурсивного спуска, где запрещаются леворекурсивные грамматики, в генераторе парсеров gppg именно леворекурсивные грамматики предпочтительны. Это связано с тем, что gppg содержит восходящий алгоритм разбора и разбирает класс грамматик LR.
- В секции определений содержится описание всех терминалов:
%token BEGIN END CYCLE INUM RNUM ID ASSIGN SEMICOLON
По этому определению в файле SimpleYacc.cs генерируется перечислимый тип
public enum Tokens {
error=1,EOF=2,BEGIN=3,END=4,CYCLE=5,INUM=6,
RNUM=7,ID=8,ASSIGN=9,SEMICOLON=10};Этот тип затем используется при лексическом анализе для возврата типа лексемы. Таким образом, необходимость в типе Tok из предыдущего проекта пропадает.
Файл лексического анализатора SimpleLex.lex
%using SimpleParser;
%using QUT.Gppg;
%using System.Linq;
%namespace SimpleScanner
Alpha [a-zA-Z_]
Digit [0-9]
AlphaDigit {Alpha}|{Digit}
INTNUM {Digit}+
REALNUM {INTNUM}\.{INTNUM}
ID {Alpha}{AlphaDigit}*
%%
{INTNUM} {
return (int)Tokens.INUM;
}
{REALNUM} {
return (int)Tokens.RNUM;
}
{ID} {
int res = ScannerHelper.GetIDToken(yytext);
return res;
}
":=" { return (int)Tokens.ASSIGN; }
";" { return (int)Tokens.SEMICOLON; }
[^ \r\n] {
LexError();
}
%{
yylloc = new LexLocation(tokLin, tokCol, tokELin, tokECol); // позиция символа (терминального или нетерминального), возвращаемая @1 @2 и т.д.
%}
%%
public override void yyerror(string format, params object[] args) // обработка синтаксических ошибок
{
var ww = args.Skip(1).Cast<string>().ToArray();
string errorMsg = string.Format("({0},{1}): Встречено {2}, а ожидалось {3}", yyline, yycol, args[0], string.Join(" или ", ww));
throw new SyntaxException(errorMsg);
}
public void LexError()
{
string errorMsg = string.Format("({0},{1}): Неизвестный символ {2}", yyline, yycol, yytext);
throw new LexException(errorMsg);
}
class ScannerHelper
{
private static Dictionary<string,int> keywords;
static ScannerHelper()
{
keywords = new Dictionary<string,int>();
keywords.Add("begin",(int)Tokens.BEGIN);
keywords.Add("end",(int)Tokens.END);
keywords.Add("cycle",(int)Tokens.CYCLE);
}
public static int GetIDToken(string s)
{
if (keywords.ContainsKey(s.ToLower())) // язык нечувствителен к регистру
return keywords[s];
else
return (int)Tokens.ID;
}
}Комментарии к файлу SimpleLex.lex
- Тип Tok из предыдущего лексического анализатора заменен на тип Tokens, автоматически генерируемый синтаксическим анализатором.
- При распознании идентификатора вначале проверяется, не совпадает ли он с одним из ключевых слов. Если нет, то возвращается Tokens.ID. Если да, то возвращается Tokens.ключевое_слово.
- Данная логика зашита в методе GetIDToken класса ScannerHelper, описанном в секции кода лексического анализатора.
- Именно такой алгоритм не позволяет использовать в качестве идентификаторов ключевые слова.
- Лексическая ошибка теперь выбрасывает исключение LexError, которое перехватывается основной программой.
- При возникновении синтаксической ошибки автоматически вызывается метод yyerror, который мы переопределяем в разделе пользовательского кода. Этот метод генерирует код синтаксической ошибки. Параметр args представляет собой массив, содержащий следующие параметры: args[0] - встреченный лексический символ (лексема), остальные элементы массива args - те лексические символы, которые ожидались (могли бы быть встречены в этом контексте)
Основная программа
using System;
using System.IO;
using System.Collections.Generic;
using SimpleScanner;
using SimpleParser;
namespace SimpleCompiler
{
public class SimpleCompilerMain
{
public static void Main()
{
string FileName = @"..\..\a.txt";
try
{
string Text = File.ReadAllText(FileName);
Scanner scanner = new Scanner();
scanner.SetSource(Text, 0);
Parser parser = new Parser(scanner);
var b = parser.Parse();
if (!b)
Console.WriteLine("Ошибка");
else Console.WriteLine("Программа распознана");
}
catch (FileNotFoundException)
{
Console.WriteLine("Файл {0} не найден", FileName);
}
catch (LexException e)
{
Console.WriteLine("Лексическая ошибка. " + e.Message);
}
catch (SyntaxException e)
{
Console.WriteLine("Синтаксическая ошибка. " + e.Message);
}
Console.ReadLine();
}
}
}Комментарии к основной программе
- Вначале создается объект класса Scanner и инициализируется текстом программы. Затем создается объект класса Parser и инициализируется сканером.
- Основной метод для распознания того, является ли программа правильной, - это метод Parser.Parse(). Если он возвращает true, то программа распознана.
- В нашем случае если программа не распознана, тот генерируется исключение.
- Классы исключений LexException и SyntaxException описаны в файле ParserHelper.cs
Основные задания (8 баллов)
- Дополнить грамматику языка оператором WHILE expr DO statement (2 балла)
- Дополнить грамматику языка оператором REPEAT stlist UNTIL expr (2 балла)
- Дополнить грамматику языка оператором FOR ID := expr TO expr do statement (2 балла)
- Дополнить грамматику языка оператором WRITE(expr) (2 балла)
Дополнительные задания (8 баллов)
- Дополнить грамматику языка оператором IF expr THEN statement ELSE statement (полная и неполная форма) (2 балла)
- Дополнить грамматику языка оператором описания вида (3 балла)
var a,b,d;
Список идентификаторов организовать аналогично списку операторов
- Дополнить грамматику языка грамматикой выражений (3 балла)
expr : T
| expr + T
| expr - T
;
T : F
| T * F
| T / F
;
F : ident
| INUM
| ( expr )
;
Обратить внимание на леворекурсивность этой грамматики.
