Создание парсеров на основе GPLEX+GPPG — различия между версиями

Текущая версия на 20:10, 10 августа 2014

К основной странице курса

Данный компилятор в виде проекта Visual Studio

Пример правильной программы

begin
  a := 5;
  b := 2;
  cycle 3 do
  begin
    c := a;
    a := a + 1
  end
end

Синтаксическое дерево ProgramTree.cs

using System.Collections.Generic;

namespace ProgramTree
{
    public enum AssignType { Assign, AssignPlus, AssignMinus, AssignMult, AssignDivide };

    public class Node // базовый класс для всех узлов    
    {
    }

    public class ExprNode : Node // базовый класс для всех выражений
    {
    }

    public class IdNode : ExprNode
    {
        public string Name { get; set; }
        public IdNode(string name) { Name = name; }
    }

    public class NumNode : ExprNode
    {
        public int Num { get; set; }
        public NumNode(int num) { Num = num; }
    }

    public class StatementNode : Node // базовый класс для всех операторов
    {
    }

    public class AssignNode : StatementNode
    {
        public IdNode Id { get; set; }
        public ExprNode Expr { get; set; }
        public AssignType AssOp { get; set; }
        public AssignNode(IdNode id, ExprNode expr, AssignType assop)
        {
            Id = id;
            Expr = expr;
            AssOp = assop;
        }
    }

    public class CycleNode : StatementNode
    {
        public ExprNode Expr { get; set; }
        public StatementNode Stat { get; set; }
        public CycleNode(ExprNode expr, StatementNode stat)
        {
            Expr = expr;
            Stat = stat;
        }
    }

    public class BlockNode : StatementNode
    {
        public List<StatementNode> StList = new List<StatementNode>();
        public BlockNode(StatementNode stat)
        {
            Add(stat);
        }
        public void Add(StatementNode stat)
        {
            StList.Add(stat);
        }
    }

}

Файл лексического анализатора SimpleLex.lex

%namespace SimpleScanner

%using SimpleParser;
%using QUT.Gppg;

Alpha 	[a-zA-Z_]
INTNUM  [0-9]+
REALNUM {INTNUM}\.{INTNUM}
ID [a-zA-Z_][a-zA-Z0-9_]* 

%%

":=" { return (int)Tokens.ASSIGN; }
";" { return (int)Tokens.SEMICOLON; }
"-=" { return (int)Tokens.ASSIGNMINUS; }
"+=" { return (int)Tokens.ASSIGNPLUS; }
"*=" { return (int)Tokens.ASSIGNMULT; }

{ID}  { 
  int res = ScannerHelper.GetIDToken(yytext);
  if (res == (int)Tokens.ID)
	yylval.sVal = yytext;
  return res;
}

{INTNUM} { 
  yylval.iVal = int.Parse(yytext); 
  return (int)Tokens.INTNUM; 
}

%{
  yylloc = new LexLocation(tokLin, tokCol, tokELin, tokECol);
%}

%%

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;
  }
  
}

Файл синтаксического анализатора SimpleYacc.yacc

%{
// Эти объявления добавляются в класс GPPGParser, представляющий собой парсер, генерируемый системой gppg
    public BlockNode root; // Корневой узел синтаксического дерева 
    public Parser(AbstractScanner<ValueType, LexLocation> scanner) : base(scanner) { }
%}

%output = SimpleYacc.cs

%union { 
			public double dVal; 
			public int iVal; 
			public string sVal; 
			public Node nVal;
			public BlockNode blVal;
       }

%using System.IO;
%using ProgramTree;

%namespace SimpleParser

%start progr

%token BEGIN END CYCLE ASSIGN ASSIGNPLUS ASSIGNMINUS ASSIGNMULT SEMICOLON
%token <iVal> INTNUM 
%token <sVal> ID

%type <nVal> expr assign st comp cycl ident
%type <blVal> stlist comp

%%

progr   : comp { root = $1; }
		;

stlist	: st 
			{ 
				$$ = new BlockNode($1 as StatementNode); 
			}
		| stlist SEMICOLON st 
			{ 
				$1.Add($3 as StatementNode); 
				$$ = $1; 
			}
		;

st	: assign { $$ = $1; }
	| comp  { $$ = $1; }
	| cycl  { $$ = $1; }
	;

ident : ID { $$ = new IdNode($1); }	
	;
	
assign 	: ident ASSIGN expr { $$ = new AssignNode($1 as IdNode, $3 as ExprNode,0); }
		;

expr	: ident  { $$ = $1 as IdNode; }
		| INTNUM { $$ = new NumNode($1); }
		;

comp	: BEGIN stlist END { $$ = $2; }
		;

cycl	: CYCLE expr st { $$ = new CycleNode($2 as ExprNode,$3 as StatementNode); }
		;
	
%%

Задания

Задание 1. Визуализировать дерево программы, добавив в каждый узел синтаксического дерева метод ToString

Задание 2. Для каждого узла синтаксического дерева реализовать метод Execute, интерпретирующий соответствующее поддерево программы. Таким образом, parser.root.Execute будет интерпретировать всю программу. Для вычисления выражений в каждом узле, производном от ExprNode, реализовать метод Eval, возвращающий целое. Для вычисления значений переменных описать

    public Dictionary<string,int> vars = new Dictionary<string,int>();

и заносить значения переменных в этот словарь.

Для визуализации работы программы после окончания программы выводить значения всех переменных.

Замечание. Интерпретацию программы root.Execute можно производить и в конце семантического действия для стартового правила:

progr   : stlist 
        { 
              root = new ProgrNode($1); 
              root.Execute();
              foreach (KeyValuePair<string,int> p in vars)
                    Console.WriteLine(p.Key+"  "+p.Value);
        }
	;

Задание 3. Дополнить грамматику языка грамматикой выражений

expr : T
     | expr + T
     ;

T    : F
     | T * F
     ;

F    : ident
     | INTNUM 
     | ( expr )
     ;

Обратить внимание на леворекурсивность этой грамматики. Реализовать узел BinaryNode с конструктором BinaryNode(leftoperand,rightoperand,operation) с методами ToString и Eval. Дополнить грамматику семантическими действиями, связанными с разбором выражений

Задание 4. Дополнить грамматику языка оператором вывода вида

print expr

Сделать print ключевым словом языка