Семантические действия при синтаксическом разборе. Построение синтаксического дерева программы — различия между версиями
Admin (обсуждение | вклад) (→Введение) |
Admin (обсуждение | вклад) (→Комментарии к файлу SimpleYacc.y) |
||
Строка 91: | Строка 91: | ||
* Синтаксическое дерево строится снизу вверх: вначале строятся листовые узлы, не имеющие потомков (например, IdNode или IntNumNode), затем по ним строятся другие узлы (например, AssignNode - по IdNode и ExprNode). | * Синтаксическое дерево строится снизу вверх: вначале строятся листовые узлы, не имеющие потомков (например, IdNode или IntNumNode), затем по ним строятся другие узлы (например, AssignNode - по IdNode и ExprNode). | ||
:Стратегия построения синтаксического дерева снизу вверх соответствует стратегии разбора снизу-вверх, принятой в парсере gppg (точнее, во всех парсерах, поддерживающих LR-грамматики) | :Стратегия построения синтаксического дерева снизу вверх соответствует стратегии разбора снизу-вверх, принятой в парсере gppg (точнее, во всех парсерах, поддерживающих LR-грамматики) | ||
+ | * $1 $2 $3 обозначают соответственно первый, второй и третий символ (нетерминал или терминал), стоящие в правой части правила, $$ - нетерминал, стоящий в левой части правила | ||
+ | * Терминалы могут иметь тип, нетерминалы обязательно имеют тип. Это так называемый '''семантический тип''', который связывается с символом. | ||
===Файл SimpleLex.lex === | ===Файл SimpleLex.lex === |
Версия 03:54, 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 обозначают соответственно первый, второй и третий символ (нетерминал или терминал), стоящие в правой части правила, $$ - нетерминал, стоящий в левой части правила
- Терминалы могут иметь тип, нетерминалы обязательно имеют тип. Это так называемый семантический тип, который связывается с символом.