语法分析器

语法分析器的构造

两个任务：

为句子（表达式）构造语法树；
检查程序（语句）中的语法错误。

主要工作：

设计函数绘图语言的文法，使其适合递归下降分析；
设计语法树的节点，用于存放表达式的语法树；
设计递归下降子程序，分析句子并构造表达式的语法树；
设计测试程序和测试用例，检验分析器是否正确。

文法

Program → ε| Program Statement SEMICO

Statement → OriginStatment | ScaleStatment
| RotStatment | ForStatment

OriginStatment → ORIGIN IS

L_BRACKET Expression COMMA Expression R_BRACKET

ScaleStatment → SCALE IS

L_BRACKET Expression COMMA Expression R_BRACKET

RotStatment → ROT IS Expression

ForStatment → FOR T
FROM Expression
TO Expression
STEP Expression
DRAW L_BRACKET Expression COMMA Expression R_BRACKET

Expression
→ Expression PLUS Expression
| Expression MINUS Expression
| Expression MUL Expression
| Expression DIV Expression
| PLUS Expression
| MINUS Expression
| Expression POWER Expression
| CONST_ID
| T
| FUNC L_BRACKET Expression R_BRACKET
| L_BRACKET Expression R_BRACKET

消除二义性

表达式中的运算 结合性 非终结符
PLUS、MINUS（二元） 左结合 Expression
MUL、DIV 左结合 Term
PLUS、MINUS（一元） 右结合 Factor
POWER 右结合 Component
（原子表达式） 无 Atom

Expression
→ Expression PLUS Expression
| Expression MINUS Expression
| Expression MUL Expression
| Expression DIV Expression
| PLUS Expression
| MINUS Expression
| Expression POWER Expression
| CONST_ID
| T
| FUNC L_BRACKET Expression R_BRACKET
| L_BRACKET Expression R_BRACKET

要引入非终结符来体现优先性还有结合性

无二义性的表达式文法

Expression → Expression PLUS Term
| Expression MINUS Term
| Term
Term → Term MUL Factor
| Term DIV Factor
| Factor
Factor → PLUS Factor
| MINUS Factor
| Component
Component → Atom POWER Component
| Atom
Atom → CONST_ID
| T
| FUNC L_BRACKET Expression R_BRACKET
| L_BRACKET Expression R_BRACKET

消除左递归和提取左因子

这样在递归下降分析中不会无限循环寻找左子树

消除Expression和Term 的左递归
Expression → Term Expression’
Expression’→ PLUS Term Expression’
| MINUS Term Expression’
|ε

Term → Factor Term’
Term’ → MUL Factor Term’
| DIV Factor Term’
|ε

改写左结合的产生式为EBNF形式（避免子程序调用）

递归子程序仅要求产生式没有左递归。

改写Program产生式：

Program → Statement SEMICO Program |ε的子程序：

void Program()
{ if (token == NONTOKEN) return;    
  Statement(); MathchToken(SEMICO); Program();
}

改写为EBNF形式，以减少不必要的子程序调用。
Program → { Statement SEMICO }的子程序：

void Program()
{  while (token != NONTOKEN) 
   { Statement(); MathchToken(SEMICO); }
} 

改写Expression产生式：

Expression →Term Expression’
Expression’ → PLUS Term Expression’
| MINUS Term Expression’ |ε

Expression’→(PLUS|MINUS)Term Expression’|ε
Program → Statement SEMICO Program |ε

Expression’ → {(PLUS|MINUS)Term }
Expression → Term {(PLUS|MINUS)Term }
Expression的递归子程序:

void Expression()
{    Term();
         while (token==PLUS || token==MINUS) 
    { MathchToken(token); Term();}
 } 

最终Expression

Expression → Term { ( PLUS | MINUS) Term }
Term → Factor { ( MUL | DIV ) Factor }
Factor → PLUS Factor | MINUS Factor | Component
Component → Atom [POWER Component]
Atom → CONST_ID
| T
| FUNC L_BRACKET Expression R_BRACKET
| L_BRACKET Expression R_BRACKET

构造Expression的语法树

通过构建语法树，才可在语义分析时通过遍历二叉树计算表达式的值。

节点

叶节点：常数、参数T等。
两个孩子的内部节点：二元运算如Plus、Mul等。
一元加：+5转化为5；
一元减：-5转化为0-5。
一个孩子的内部节点：函数调用，如cos(t)等。

其实用c/c++做会较为简单，因为指针的存在二叉树很方便。java这里我构建了一个类，其中left,right是左子树或右子树的数组序，其实还是通过数组的序来确定这颗树的。

这里代码在语义分析处附上，因为我将语义分析紧接着语法分析做了。因为比较方便,不用重复创建使用Tokens。