Семантические действия при синтаксическом разборе. Построение синтаксического дерева программы

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск

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

Код проекта

Комплект для практического занятия скачиваем отсюда.

Введение

Синтаксически управляемая трансляция состоит в том, что при разборе текста программы на каждое распознанное правило грамматики выполняется некоторое действие. Данные действия придают смысл трансляции (переводу) и поэтому мы называем их семантическими. Семантические действия записываются в .y-файле после правил в фигурных скобках и представляют собой код программы на C# (целевом языке компилятора).

Как правило, при трансляции программа переводится в другую форму, более приспособленную для анализа, дальнейших преобразований и генерации кода.

Мы будем переводить текст программы в так называемое синтаксическое дерево. Если синтаксическое дерево построено, то программа синтаксически правильная, и ее можно подвергать дальнейшей обработке.

В синтаксическое дерево включаются узлы, соответствующие всем синтаксическим конструкциям языка. Атрибутами этих узлов являются их существенные характеристики. Например, для узла оператора присваивания AssignNode такими атрибутами являются IdNode - идентификатор в левой части оператора присваивания и ExprNode - выражение в правой части оператора присваивания.

Синтаксическое дерево программы (или AST - Abstract Syntax Tree) отличается от дерева разбора тем, что в него не добавляются несущественные атрибуты - например, ключевые слова.

Обсуждение кода мы начнем с .y-файла. Грамматика в нем не поменялась.

Файл SimpleYacc.y

%{
// Эти объявления добавляются в класс 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 ExprNode eVal;
	public StatementNode stVal;
	public BlockNode blVal;
       }

%using ProgramTree;

%namespace SimpleParser

%token BEGIN END CYCLE ASSIGN SEMICOLON
%token <iVal> INUM 
%token <dVal> RNUM 
%token <sVal> ID

%type <eVal> expr ident 
%type <stVal> assign statement cycle 
%type <blVal> stlist block

%%

progr   : block { root = $1; }
	;

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

statement: assign { $$ = $1; }
	| block   { $$ = $1; }
	| cycle   { $$ = $1; }
	;

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

expr	: ident  { $$ = $1 as IdNode; }
	| INUM { $$ = new IntNumNode($1); }
	;

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

cycle	: CYCLE expr statement { $$ = new CycleNode($2, $3); }
	;
	
%%

Комментарии к файлу SimpleYacc.y

  • Данный файл описывает ту же грамматику, что и файл с прошлого занятия. Поэтому сконцентрируемся на отличиях.
  • Самое важное отличие - наличие семантических правил, которые записаны после правил грамматики в фигурных скобках и являются командами, конструирующими узлы синтаксического дерева.
  • Синтаксическое дерево строится снизу вверх: вначале строятся листовые узлы, не имеющие потомков (например, IdNode или IntNumNode), затем по ним строятся другие узлы (например, AssignNode - по IdNode и ExprNode).
Стратегия построения синтаксического дерева снизу вверх соответствует стратегии разбора снизу-вверх, принятой в парсере gppg (точнее, во всех парсерах, поддерживающих LR-грамматики)
  • Корень синтаксического дерева записывается в поле root класса Parser
  • $1 $2 $3 обозначают соответственно первый, второй и третий символ (нетерминал или терминал), стоящие в правой части правила, $$ - нетерминал, стоящий в левой части правила

Главное

  • Запись
%union { 
	public double dVal; 
	public int iVal; 
	public string sVal; 
	public Node nVal;
	public ExprNode eVal;
	public StatementNode stVal;
	public BlockNode blVal;
       }

переводится в код

public struct ValueType
{ 
  public double dVal; 
  public int iVal; 
  public string sVal; 
  public Node nVal;
  public ExprNode eVal;
  public StatementNode stVal;
  public BlockNode blVal;
}

в файле SimpleYacc.cs.

  • Терминалы могут иметь тип, нетерминалы обязательно имеют тип. Это так называемый семантический тип, который связывается с символом. Если символ имеет тип, то выражение $что-то, связанное с символом, возвращает значение этого типа.
  • Типы терминалов описываются в строке, начинающейся с %token, типы терминалов - в строке, начинающейся с %type:
%token <iVal> INUM 
%token <dVal> RNUM 
%token <sVal> ID

%type <eVal> expr ident 
%type <stVal> assign statement cycle 
%type <blVal> stlist block

В угловых скобках здесь указываются имя одного из полей структуры ValueType.

Например, запись

%token <iVal> INUM 

означает, что терминал INUM будет соответствовать полю iVal объекта класса ValueType, которое имеет тип int:

public int iVal;

Запись

%type <eVal> expr ident 
%type <stVal> assign statement cycle 
%type <blVal> stlist block

означает, что нетерминалы expr ident имеют тип ExprNode, нетерминалы assign statement cycle имеют тип StatementNode и нетерминалы stlist block - тип BlockNode.

  • Рассмотрим правило
statement: block { $$ = $1; }

Нетрудно видеть, что $$ и $1, соответствующие нетерминалам statement и assign, имеют соответственно типы StatementNode и BlockNode, т.е. совместимы по присваиванию. Соответствующий код в файле SimpleYacc.cs имеет вид:

case 6: // statement -> block
{ CurrentSemanticValue.stVal = ValueStack[ValueStack.Depth-1].blVal; }
  • Терминалы, связанные с $1, $2 и т.д., должны получать значения на этапе лексического анализа. Это будет описано в следующем пункте.
  • Единственное место, где требуется понижающее приведение типа - это:
$$ = new AssignNode($1 as IdNode, $3);

Здесь $1 имеет тип ExprNode, но хранит тип IdNode.

Создание списков

Рассмотрим код

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

ответственный за создание списка операторов.

Это - часто встречаемый шаблон, задаваемый леворекурсивной грамматикой. Наша задача - накопить элементы списка в некотором контейнере и в итоге вернуть этот контейнер в $$.

В данном примере таким контейнером выступает класс BlockNode, хранящий список StatementNode и имеющий метод Add(StatementNode st)

При переходе по первой ветви правила объект BlockNode создается и возвращается в $$. При наличии нескольких statements именно эта ветвь сработает первой (если грамматика будет праворекурсивной, то она сработает последней!!!).

При переходе по второй ветви правила stlist в правой части будет соответствовать $1 и хранить значение типа BlockNode, инициализированное на предыдущих шагах. Мы добавим в него следующий statement:

$1.Add($3); 

И, наконец, мы выполним действие

 $$ = $1; 

которое означает, что мы передаем ссылку на объект BlockNode, хранящийся в $1, в $$.

Эквивалентный код, делающий то же самое:

$$ = $1; 
$$.Add($3);

Файл SimpleLex.lex

В файле SimpleLex.lex изменен лишь данный участок:

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

{REALNUM} { 
  yylval.dVal = double.Parse(yytext); 
  return (int)Tokens.RNUM;
}

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

Комментарии к файлу SimpleLex.lex

  • В типе Scanner определен ряд свойств, основными из которых являются:
    • yytext - текст лексемы,
    • yylval - лексическое значение лексемы (имеет тип ValueType) - аналог LexValueInt и LexValueDouble из предыдущего проекта,
    • yylloc - позиция лексемы, описываемая типом LexLocation.
  • Типы терминалов устанавливаются в файле SimpleYacc.cs, где определена структура %union:
%token <iVal> INUM 
%token <dVal> RNUM 
%token <sVal> ID

Отсюда следует, что INUM связано с полем yylval.iVal, RNUM - с полем yylval.rVal, ID связано с полем yylval.sVal.

  • Лексические значения этим полям присваиваются до возврата вида терминала, например:
yylval.iVal = int.Parse(yytext);

Файл 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 IntNumNode : ExprNode
    {
        public int Num { get; set; }
        public IntNumNode(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 = AssignType.Assign)
        {
            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);
        }
    }

}

Комментарии к файлу ProgramTree.cs

  • Предок всех узлов - узел Node, предок всех узлов выражений - ExprNode, предок всех узлов операторов - StatementNode.
  • Листовыми узлами являются IdNode и IntNumNode.

Основные задания (8 баллов - по 2 балла задание)

  • Реализовать построение узла синтаксического дерева WhileNode для оператора WHILE expr DO statement
  • Реализовать построение узла синтаксического дерева RepeatNode для оператора REPEAT stlist UNTIL expr
  • Реализовать построение узла синтаксического дерева ForNode для оператора FOR ID := expr TO expr do statement
  • Реализовать построение узла синтаксического дерева WriteNode для оператора WRITE(expr)

Дополнительные задания (8 баллов)

  • Реализовать построение узла синтаксического дерева IfNode для оператора IF expr THEN statement ELSE statement (полная и неполная форма) (2 балл)
  • Реализовать построение узла синтаксического дерева VarDefNode для оператора описания (3 балла)
 var a,b,d;
  • Реализовать построение узла синтаксического дерева BinaryNode для грамматики выражений с конструктором BinaryNode(left,right,char operation) (3 балла)