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

Версия 03:57, 18 августа 2014

Введение

Синтаксически управляемая трансляция состоит в том, что при разборе текста программы на каждое распознанное правило грамматики выполняется некоторое действие. Данные действия придают смысл трансляции (переводу) и поэтому мы называем их семантическими. Семантические действия записываются в .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, 0); }
	;

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-грамматики)

• $1 $2 $3 обозначают соответственно первый, второй и третий символ (нетерминал или терминал), стоящие в правой части правила, $$ - нетерминал, стоящий в левой части правила

Главное

• Терминалы могут иметь тип, нетерминалы обязательно имеют тип. Это так называемый семантический тип, который связывается с символом. Если символ имеет тип, то выражение $что-то, связанное с символом, возвращает значение этого типа

Файл SimpleLex.lex

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

Основные задания

Дополнительные задания