Создание синтаксического анализатора с помощью программы 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 )
     ;

Обратить внимание на леворекурсивность этой грамматики.