Просмотр исходного текста страницы Создание синтаксического анализатора с помощью программы GPPG

[[Страница_курса_%22Методы_построения_компиляторов%22| К основной странице курса]]
__NOTOC__
===Общие комментарии===
*В данном проекте мы создадим front-end компилятор с помощью [http://gppg.codeplex.com/ '''генератора парсеров gppg'''].
*Комплект для практического занятия [http://pascalabc.net/downloads/CompilerConstruction/SimpleLanguage0.zip скачиваем отсюда]. 
*Для автоматического создания парсера создаются файлы SimpleLex.lex (описание лексического анализатора) и SimpleYacc.y (описание синтаксического анализатора).
*Код лексического и синтаксического анализаторов создаются на C# запуском командного файла generateParserScanner.bat со следующим содержимым:
 gplex.exe /unicode SimpleLex.lex
 gppg.exe /no-lines /gplex SimpleYacc.y
Параметр /gplex здесь означает, что gppg работает в связке с gplex.

===Файл синтаксического анализатора SimpleYacc.y=== 
<source lang="Csharp">
%{
// Эти объявления добавляются в класс 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 
	;
	
%%
</source>
====Формат .y-файла====

 Определения
 %%
 Правила
 %%
 Пользовательский код

===Комментарии к файлу SimpleYacc.y===
*Файл синтаксического анализатора '''значительно проще и понятнее''' [[Создание синтаксического анализатора простого языка программирования|рукописного файла синтаксического анализатора]]. Он не содержит кода и содержит лишь спецификацию грамматики. 
*Секция правил представляет собой описание грамматики языка. Пример правильной программы, удовлетворяющей этой грамматике:
 begin
   b := 2;
   a := b;
   cycle 3
   begin
     a := c;
     c := 1
   end
 end
*Определение последовательности операторов - леворекурсивно:
<source lang="Csharp">stlist	: statement 
	| stlist SEMICOLON statement 
	;
</source>
В отличие от создания синтаксического анализатора методом рекурсивного спуска, где запрещаются леворекурсивные грамматики, в генераторе парсеров gppg 
именно леворекурсивные грамматики предпочтительны. Это связано с тем, что gppg содержит восходящий алгоритм разбора и разбирает класс грамматик LR.

* В секции определений содержится описание всех терминалов:

 %token BEGIN END CYCLE INUM RNUM ID ASSIGN SEMICOLON
По этому определению в файле SimpleYacc.cs генерируется перечислимый тип
<source lang="Csharp">public enum Tokens {
    error=1,EOF=2,BEGIN=3,END=4,CYCLE=5,INUM=6,
    RNUM=7,ID=8,ASSIGN=9,SEMICOLON=10};
</source>
Этот тип затем используется при лексическом анализе для возврата типа лексемы. Таким образом, необходимость в типе Tok из предыдущего проекта пропадает.

===Файл лексического анализатора SimpleLex.lex===
<source lang="Csharp">
%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;
  }
}
</source>

===Комментарии к файлу SimpleLex.lex===
*Тип Tok из предыдущего лексического анализатора заменен на тип Tokens, автоматически генерируемый синтаксическим анализатором.
*При распознании идентификатора вначале проверяется, не совпадает ли он с одним из ключевых слов. Если нет, то возвращается Tokens.ID. Если да, то возвращается Tokens.ключевое_слово.
:Данная логика зашита в методе GetIDToken класса ScannerHelper, описанном в секции кода лексического анализатора.
:Именно такой алгоритм не позволяет использовать в качестве идентификаторов ключевые слова.
*Лексическая ошибка теперь выбрасывает исключение LexError, которое перехватывается основной программой.
*При возникновении синтаксической ошибки автоматически вызывается метод yyerror, который мы переопределяем в разделе пользовательского кода. Этот метод генерирует код синтаксической ошибки. Параметр args представляет собой массив, содержащий следующие параметры: args[0] - встреченный лексический символ (лексема), остальные элементы массива args - те лексические символы, которые ожидались (могли бы быть встречены в этом контексте)

===Основная программа===
<source lang="Csharp">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();
        }

    }
}
</source>

===Комментарии к основной программе===
* Вначале создается объект класса 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 балла)'''
<pre>
expr : T
     | expr + T
     | expr - T
     ;

T    : F
     | T * F
     | T / F
     ;

F    : ident
     | INUM 
     | ( expr )
     ;
</pre>
Обратить внимание на леворекурсивность этой грамматики.