重建AST

利用antlr完成了語法分析之后,就需要進行語義分析了。

詞法與語法分析相對固定,利用工具就可以完成,但語義分析則需要設(shè)計這么語言或者腳本的人員來完善它。

語義即語言最終需要表達的含義。

我們先來看一個自然語言例子,以我們熟悉的中文為例:我是程序猿！首先我們通過詞法分析工具將他拆分開：我,是,程序猿。通過語法分析將它建立成一個AST節(jié)點

接下來我們通過兩種不能的算法將它運算一下看看會得到什么樣的結(jié)果。

第一種算法:左子節(jié)點+根節(jié)點+右子節(jié)點,運算結(jié)果是“我是程序猿”。

第二種算法:右子節(jié)點+根節(jié)點+左子節(jié)點，運算結(jié)果是“程序猿是我”。

可以得出,不同的運算規(guī)則得到的結(jié)果的含義是不一樣的,這也是為什么語義分析需要設(shè)計人員自己來實現(xiàn)了。但是我們不能隨意運算,運算也要符合規(guī)則。如果運算規(guī)則是：根節(jié)點+左子節(jié)點+右子節(jié)點則得出的結(jié)果就是錯誤的了。

從上面的自然語言例子不難得出,我們設(shè)計用于與計算機打交道的語言也是一樣的，計算機的目的是計算。

一元表達式，二元表達式，三元表達式他們都有一個根節(jié)點是計算符號，子節(jié)點是需要計算的表達式。

給這個節(jié)點賦予怎么樣的含義完成取決于設(shè)計這們語言的人。

我已經(jīng)將第三節(jié)中的語法分析規(guī)則與詞法分析規(guī)則進行了完善：

「將原來的點取值改成了方括號取值，完善了小括號優(yōu)先級語法。具體規(guī)則代碼如下：」

lexer grammar DynamicDSLLexer;
//關(guān)鍵字
If: 'if';
FOR: 'for';
WHILE: 'while';
IN: 'in';
/// 基礎(chǔ)數(shù)據(jù)類型
Int: 'int';
Double: 'double';
Float: 'float';
String: 'string';
Bool: 'bool';
//字面量
IntLiteral: [0-9]+;
DoubleLiteral: [0-9]+ Dot [0-9]+;
StringLiteral: ('"' .*? '"') | ('\\'' .*? '\\''); //字符串字面量
True: 'true';
False: 'false';
//操作符
AssignmentOP: '=';
RelationalOP: '>' | '>=' | '<' | '<=';
Star: '*';
Plus: '+';
Sharp: '#';
SemiColon: ';';
Dot: '.';
Comm: ',';
LeftBracket: '[';
RightBracket: ']';
LeftBrace: '{';
RightBrace: '}';
LeftParen: '(';
RightParen: ')';
//標識符
Id: [a-zA-Z_] ([a-zA-Z_] | [0-9])*;
//空白字符，拋棄
WS: [ \\t\\r\\n]+ -> skip;

grammar DynamicDSLScript;
import DynamicDSLLexer;

/// 表達式,按右邊產(chǎn)生式的順序來依次優(yōu)先推導(dǎo)
expression:
 primary
 | LSB = '[' expression RSB = ']'
 | expression LSB = '[' expression RSB = ']'
 | LB = '(' expression RB = ')'
 | expression LB = '(' expression RB = ')'
 | FOR Id IN Id
 | declare = (Int | Double | Float | String | Bool) Id assign = '=' expression // 申明變量并賦值
 | declare = (Int | Double | Float | String | Bool) Id /// 申明變量,沒有賦值
 | Id assign = '=' expression /// 賦值,需要查變量是否申明
 | expression postfix = ('++' | '--')
 | prefix = ('++' | '--') expression
 | expression bop = ('*' | '/' | '%') expression
 | expression bop = ('+' | '-') expression
 | expression bop = ('<' | '<=' | '>' | '>=') expression
 | expression bop = ('==' | '!=') expression
 | expression bop = ('&&' | '||') expression
 | expression bop = '?' expression bop = ':' expression;

primary:
 Id
 | StringLiteral
 | IntLiteral
 | DoubleLiteral
 | TF = (True | False);

我們來看這樣一個例子: (3+5) *(123-5) / 2 + [object][age] 分的語法分析結(jié)果是這樣的：

這是antlr分析出來的結(jié)果,現(xiàn)在我們需要對這個分析結(jié)果進行重建,將antlr分析的AST重建成更容易理解與運算的AST。重建后的結(jié)果如下:

每一個節(jié)點都是我們在語法規(guī)則文件中定義的一種推導(dǎo)規(guī)則,要計算根節(jié)點,就必須先計算子節(jié)點，通過遞歸的方式從子節(jié)點到根節(jié)點運算的過程就是:深度優(yōu)先遍歷。通過對這個AST進行深度優(yōu)先遍歷，得到最終的運算符。

A：加減乘除運算就是將左右的結(jié)果作對應(yīng)的運算

B: []取舍則是將先取值運算的作為后取值運算的子節(jié)點,所以它的推導(dǎo)式是這樣的：

| LSB = '[' expression RSB = ']'
 | expression LSB = '[' expression RSB = ']'

首先嘗試推導(dǎo)是否是一個獨立的[]運算，比如這樣[object]。

我們在這里賦予它的含義是,從棧幀上下文中去尋找名稱為object的變量,并取出它的值。

如果是連續(xù)的[]運算,比如[object][age]則我們使用上面的第一條推導(dǎo)式發(fā)現(xiàn)推導(dǎo)是失敗的,

接著嘗試第二條推導(dǎo)式,首先將[age]推導(dǎo)出來成為一個節(jié)點，接著[object]繼續(xù)重新按第一條再次推導(dǎo),發(fā)現(xiàn)推導(dǎo)成功，再將這個節(jié)點作用[age]推導(dǎo)出來的子節(jié)點。

在求值的時候就會優(yōu)先求子節(jié)點[object]得到的結(jié)果作為[age]節(jié)點的上下文變量環(huán)境繼續(xù)尋找名稱是age的變量的值。

Antlr的語法推導(dǎo)是按定義的順序進行推導(dǎo)的,首先推導(dǎo)定義在前面的規(guī)則，推導(dǎo)失敗再繼續(xù)推導(dǎo)后面的規(guī)則。

推導(dǎo)成功立即建立一個AST節(jié)點，推導(dǎo)未完成的部分繼續(xù)進行推導(dǎo)并成功后變成此節(jié)點的子節(jié)點。

每增加一種推導(dǎo)規(guī)則我們就增加一種運算節(jié)點。

接下來,我們將利用C++來完成對AST的節(jié)點實現(xiàn),實現(xiàn)一個簡單的節(jié)點與數(shù)據(jù)類型模型。完成AST的C++實現(xiàn)與運算。

如果你覺得有用,請分享給更多的人。