编译原理

stateDiagram-v2  源代码 --> 词法分析  state 前端 {    词法分析 --> 语法分析    语法分析 --> 语义分析  }  语义分析 --> 生成中间代码  state 后端 {    生成中间代码 --> 优化    优化 --> 生成目标代码  }

词法分析

有限自动机

要实现一个词法分析器，首先需要写出每个词法的正则表达式，并画出有限自动机，之后，只要用代码表示这种状态迁移过程就可以了

age >= 45 的此法解析自动机：

stateDiagram-v2  初始 --> 比较操作符>: >  比较操作符> --> 比较操作符>=: =  初始 --> ID: 字母  ID --> ID: 字母或数字  初始 --> 数字字面量: 数字  数字字面量 --> 数字字面量: 数字

DfaState newState = DfaState.Initial;if (isAlpha(ch)) {              //第一个字符是字母    newState = DfaState.Id; //进入Id状态    token.type = TokenType.Identifier;    tokenText.append(ch);} else if (isDigit(ch)) {       //第一个字符是数字    newState = DfaState.IntLiteral;    token.type = TokenType.IntLiteral;    tokenText.append(ch);} else if (ch == '>') {         //第一个字符是>    newState = DfaState.GT;    token.type = TokenType.GT;    tokenText.append(ch);}

使用正则表达式描述词法：

Id :        [a-zA-Z_] ([a-zA-Z_] | [0-9])*IntLiteral: [0-9]+GT :        '>'GE :        '>='

语法分析

语法规则描述

BNF:

add ::= mul | add + mulmul ::= pri | mul * pripri ::= Id | Num | (add) 

扩展BNF（EBNF）：

// 会用到类似正则表达式的一些写法add -> mul (+ mul)*

上下文无关文法

上下文无关指的是无论在任何情况下，文法的推导规则都是一样的

描述整数加法与乘法的文法，在解析后，可以形成一颗AST：

additiveExpression    :   multiplicativeExpression    |   additiveExpression Plus multiplicativeExpression    ;multiplicativeExpression    :   IntLiteral    |   multiplicativeExpression Star IntLiteral    ;

“2+3*5” 的推导过程：

-->additiveExpression + multiplicativeExpression-->multiplicativeExpression + multiplicativeExpression-->IntLiteral + multiplicativeExpression-->IntLiteral + multiplicativeExpression * IntLiteral -->IntLiteral + IntLiteral * IntLiteral

递归下降

上级文法嵌套下级文法，上级的算法调用下级的算法

消除左递归：

对于加法与乘法的文法：

add -> mul | add + mul   

会陷入无限递归，那就引入一个终止条件，也就是空集来终止递归：

add -> mul add'add' -> + mul add' | ε

// EBNP表达add -> mul (+ mul)* 

Antlr

词法规则文件：

lexer grammar Hello;  //lexer关键字意味着这是一个词法规则文件，要与文件名相同。@header {package antlrtest;}//关键字If :               'if' | '如果';   //可以在程序里用‘如果’来代替'if'Int :              'int';//常量IntLiteral:        [0-9]+;StringLiteral:      '"' .*? '"' ;  //字符串常量//操作符AssignmentOP:       '=' ;    RelationalOP:       '=='|'>'|'>='|'<' |'<=' ;    Star:               '*';Plus:               '+';Sharp:              '#';SemiColon:          ';';Dot:                '.';Comm:               ',';LeftBracket :       '[';RightBracket:       ']';LeftBrace:          '{';RightBrace:         '}';LeftParen:          '(';RightParen:         ')';//标识符Id :                [a-zA-Z_] ([a-zA-Z_] | [0-9])*;//空白字符，抛弃Whitespace:         [ \t]+ -> skip;Newline:            ( '\r' '\n'?|'\n')-> skip;

// 语法分析器expression    :   assignmentExpression    |   expression ',' assignmentExpression    ;assignmentExpression    :   additiveExpression    |   Identifier assignmentOperator additiveExpression    ;assignmentOperator    :   '='    |   '*='    |  '/='    |   '%='    |   '+='    |   '-='    ;additiveExpression    :   multiplicativeExpression    |   additiveExpression '+' multiplicativeExpression    |   additiveExpression '-' multiplicativeExpression    ;multiplicativeExpression    :   primaryExpression    |   multiplicativeExpression '*' primaryExpression    |   multiplicativeExpression '/' primaryExpression    |   multiplicativeExpression '%' primaryExpression    ;

# 生成词法分析器的java源码antlr Hello.g4# 生成语法分析器antlr PlayScript.g4# 输入表达式查看ASTgrun antlrtest.PlayScript expression -gui