语法解析器首先就是构建我们的语法解析规则. 将我们通过词法解析获取的 Token 数据转换为一个语法树.
image.png
上图引用自: https://time.geekbang.org/column/article/119891

原理算法分析

算法本身是一个下降的过程
image.png

语法规则

  1. program: statement+;
  3. statement: intDeclaration | expressionStatement | assignmentStatement;
  5. intDeclaration : 'int' Identifier ( '=' additiveExpression)? ';';
  6. expressionStatement : additiveExpression ';';
  7. assignmentStatement : Identifier '=' additiveExpression ';';
  9. additiveExpression : multiplicativeExpression ( (+|-)  multiplicativeExpression )*
  11. multiplicativeExpression: primaryExpression ( (* | /) primaryExpression)*
  13. primaryExpression : Identifier | IntLiteral | '(' additiveExpression ')';
  1. 程序由 一个或多个 **statement** 组成.
  2. **statement** 由 **intDeclaration**(变量声明) **expressionStatement**(表达式语句) 或 **assignmentStatement**(赋值语句) 组成 ,三者取其一.
  3. **intDeclaration**(变量声明)
    1. int 开头
    2. 空格
    3. **Identifier** 类型的 Token
    4. 之后可以有 = 和 **additiveExpression**(加法表达式)
    5. 末尾为 分号
  4. **expressionStatement**(表达式语句) 只有 **additiveExpression**(加法表达式) + 末尾分号
  5. **assignmentStatement**(赋值语句)
    1. **Identifier** 类型的 Token
    2. =
    3. **additiveExpression**(加法表达式)
    4. 末尾为 分号
  6. **additiveExpression**(加法表达式)
    1. 一个 **multiplicativeExpression**(乘法表达式)
    2. 加号或者减号
    3. 一个 **multiplicativeExpression**(乘法表达式)
    4. b 和 c 可以匹配0次或者多次
  7. **multiplicativeExpression**(乘法表达式)
    1. 一个**primaryExpression**(主表达式)
    2. 乘号或者除号
    3. 一个**primaryExpression**(主表达式)
    4. b 和 c 可以匹配0次或者多次
  8. **primaryExpression**(主表达式) 有变量 , 数字字面量 或者 括号 + **additiveExpression**(加法表达式) 组成

    数据结构设计

  • ASTNode 接口

    1. type Node interface {
    2.   Parent() Node
    4.   Children() []Node
    6.   Type() Type
    8.   Text() string
    9. }

  • 节点类型 ```go type Type int

const ( Program Type = iota //程序入口，根节点

  1. IntDeclaration //整型变量声明
  2. ExpressionStmt //表达式语句，即表达式后面跟个分号
  3. AssignmentStmt //赋值语句
  5. Primary        //基础表达式
  6. Multiplicative //乘法表达式
  7. Additive       //加法表达式
  9. Identifier //标识符
  10. IntLiteral //整型字面量

) ```