重建AST

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

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

語義即語言最終需要表達(dá)的含義。

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

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

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

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

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

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

一元表達(dá)式，二元表達(dá)式，三元表達(dá)式他們都有一個(gè)根節(jié)點(diǎn)是計(jì)算符號(hào)，子節(jié)點(diǎn)是需要計(jì)算的表達(dá)式。

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

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

「將原來的點(diǎn)取值改成了方括號(hào)取值，完善了小括號(hào)優(yōu)先級(jí)語法。具體規(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: ')';
//標(biāo)識(shí)符
Id: [a-zA-Z_] ([a-zA-Z_] | [0-9])*;
//空白字符，拋棄
WS: [ \\t\\r\\n]+ -> skip;

grammar DynamicDSLScript;
import DynamicDSLLexer;

/// 表達(dá)式,按右邊產(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);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如果你覺得有用,請(qǐng)分享給更多的人。