词法&语法分析基础

2020-08-29
9 min read
techs

将文本转化为可以执行的程序一般需要词法分析、语法分析、语义分析和后端处理等步骤。从 0 开始写这些工具比较耗时，所以一般使用现成的工具生成语法解析代码

  • 语言：一个语言就是一个句子集合（ a set of sentences） ， 用 L 表示， 任何由句子组成的集合都可以被称为一个语言
  • 编译：编译就是给定两个句子集合 Ls （ 源语言） 和 Lo （ 目标语言） 以及一个句子 ss ， 判断 ss 是否属于 Ls ， 以及在 Lo 中寻找出一个句子 so ， 其意义和 ss 相同
  • 编译器前端：编译器前端用于将源码转化为中间代码，比如《自己动手写编译器》使用 Flex&Bison 将源码转化为 Pcode
  • 编译器后端：将中间代码转化为目标机器可执行的代码，编译器分前后端是为了工具的复用，新出现的语言，只要实现前端就可以了

词法分析

处理语言的第一个组成部分是词法分析器（lexical analyzer、lexer 或者 scanner），词法分析将文本分割为单词（token）序列。词法分析可用的工具有 lex 和 Flex ，后者是前者的开源增强版本。词法分析器相对简单，所以正式的编程语言一般都不会使用 lex 等工具

最简单的词法分析方式是直接扫描法，在扫描字符串的过程中判断与解析 token，这类方法实现简单但比较难扩展，而且效率也不高，部分 token 的判断需要多次扫描

正则表达式

绝大部分语言的词法分析工具是正则表达式，无论是 flex 等工具还是手写词法分析器，正则表达式一般都是基础。正则表达式的实现使用的是 FA，即有限状态自动机（Finate Automaton）

它的工作过程是：首先自动机处于初始状态，之后它开始读入字符串，每读入一个字符，它都根据当前状态和读入字符转换到下一状态，直到字符串结束，若此时自动机处于其接受状态，则表示该字符串被此自动机接受，即匹配成功。Flex 是一个快速词法分析生成器， 它可以将用户用正则表达式写的分词匹配模式构造成一个有限状态自动机（一个 C 函数）

语法分析

词法分析后需要判断这些单词的组合方式是否满足我们当初设定的语法要求，比如 54 ! b 这样的的组合是违反语法规则的。语法分析常用的工具有 yacc 和 bison，后者是前者的开源版本

  • 终结符/非终结符，词法分割中的最小单元，也是语法分析中的最小单元，例如一个整数，一个运算符等。表达式由终结符组成，其是可以分割的，故称为非终结符

抽象语法树（AST）

抽象语法树（Abstract Syntax Tree，AST）是表示程序结构的数据结构，构造语法树的过程称为语法分析。以 1+3*(4-1)+2 为例，语法分析后生成的语法树形如：

graph LR
	A[+]
	C[+]
	B[2]
	E[*]
	D[1]
	F[3]
	G[-]
	H[4]
	I[1]
	
	A --> B
	A --> C
	C --> D
	C --> E
	E --> F
	E --> G
	G --> H
	G --> I

依次求解子树的值可得整个表达式的值

自顶向下（LL(1)）

略（参考）

自底向上（LR & LALR(1)）

自底向上分析的顺序和自顶向下分析的顺序刚好相反，从给定的句子开始，不断的挑选出合适的产生式，将中间句子中的子串折叠为非终结符，最终折叠到起始符号 。自底向上分析法的解析力量比自顶向下分析法要强大的多，和自顶向下分析法相比，它可以解析更为复杂、更为广泛的语法

移进&归约

LR 是典型的自底向上分析法，其基本思路如下：

  1. 起始状态：栈内无任何符号，可以认为栈上是一个空串
  2. 每个分析步：如果栈上的符号串不可折叠，则从输入流中读入一个符号（shift，移进），放到栈上的符号串的最后；否则，折叠此符号串，将需折叠的子串的所有符号出栈，并将折叠得到的非终结符放到栈的末尾 （reduce，折叠，即归约）

这就是 LR 分析法的命名原因，第一个 L 表示从左向右扫描输入流，第二个 R 表示每次折叠一定发生在栈上符号串的最右边 。LR(0) 表示 shift 过程中不 lookahead，即不预看下一个符号，LR(1) 表示 Shift 过程预读 1 个符合，LR(1) 比 LR(0) 的适用范围要广

将相似状态合并（Merge）起来的分析法称为 LALR(1) 分析法，这是很多编译器所采用的分析方法。Bison 读取用户提供的语法的产生式，生成一个 C 语言格式的 LALR(1) 动作表，并将其包含进一个名为 yyparse 的 C 函数，这个函数的作用就是利用这个动作表来解析 token stream ，而这个 token stream 是由 flex 生成的词法分析器扫描源程序得到。下面以 Bison 为例1来说明移进和归约的流程，先给出 Bison 语法描述

statement:   NAME '=' expression
expression:  NUMBER '+' NUMBER
           | NUMBER '−' NUMBER

对于表达式 fred = 12 + 13，已知表达式 fred = expression，则分析器栈的变化如下（每次读一个 token，然后尝试归约）：

fred
fred =
fred = 12
fred = 12 +
fred = 12 + 13
fred = expression

巴科斯范式（BNF）

编译领域常用巴科斯范式（Backus-Naur Form，BNF）来描述语言的语法规则，BNF 与正则表达式很类似，但 BNF 对递归的支持更加丰富且 BNF 以单词为最小匹配单元（正则表达式则是字符）。BNF 示例（不同实现语法不同）：

factor:    NUMBER | "(" expresion ")"
term:      factor { ("*" | "/") factor }
expresion: term { ("+" | "-") term }

BNF 的实现各有不同，Bison 示例可以参考 这里

Flex&Bison 简介

如上文介绍，Flex2 是词法分析工具，Bison3 是语法分析工具。Flex 将输入的文本流转化为 token 序列，Bison 分析这些 token 并基于逻辑（语法）进行组合。Flex 和 Bison 的详细用法可以参考书籍 《flex与bison（中文版）》。编写 Flex&Bison 脚本的时候要注意空格，因为 Flex&Bison 是比较老的工具，所以其自身 Token 以空格分隔，下面两行 Flex 正则在编译后的行为是不一样的（第二行多一个空格）

[0-9]+"."[0-9]*{EXP}?|"."?[0-9]+{EXP}? { yylval.d = atof(yytext); return NUMBER; }
[0-9]+"."[0-9]*{EXP}? |"."?[0-9]+{EXP}? { yylval.d = atof(yytext); return NUMBER; }

Flex 使用正则表达式匹配词元（token），而部分字符串可以被多个正则匹配到，那么 Flex 就默认了以下两条规则：使用最大一口原则，一次匹配最长的串 / 优先匹配最先出现的模式。下表列出了一些 Flex 常见函数和变量

Flex

Flex 编译 lex 文件时可以指定一些 option 来修改代码行为，命令行的 option 也有 lex 脚本中对应的配置项。Flex 作为词法分析器常与语法分析工具配合使用，故两边有一些变量约定。从字符流中批评到指定模式（正则）后，flex 会将匹配到的字符串保存在 yytext 数组中（词元内容）并返回一个整数（词元编号）。flex 也可以返回某个字符，故自定义词元编号要从 258 开始，细节可以参考 Bison 文档

另一个 flex 全局变量是 yylval 可用于 flex&bison 数据交互，yylval 默认为整型变量，不过可以通过 %union 指令修改为联合体，从而可以保存不同类型的数据

编译选项 备注
%option prefix="sql_" 1. 修改 flex 变量的前缀（默认为 yy，例如 yylval->sql_lval）
2. 对应的命令行选项为：--prefix=sql_
%option nodefault
%opiton rerntrant		 1. 当输入无法被给定的规则完全匹配时，词法分析器可以报告一个错误
函数&变量 备注
yytext / yylineno / yylval / 1. yytext 指向本次匹配的输入文本
INITIAL / 1. INITIAL 是 Flex 解析的初始状态
ECHO / input / unput / 1. ECHO 等价于 fprintf(yyout, "%s", yytext);
yyin
yyrestart(f_ptr);		 1. flex 默认从标准输入（stdin）获取数据
2. 可以在启动程序时修改：yyin=fopen("file_path", "r")
3. 或者调用 yyrestart 函数
yy_scan_string(...)
#define YY_INPUT(buff, res, buffsize) ...		 1. flex 提供了一些 IO 操作函数，以提升性能
2. 每当 flex 发现缓冲区空，则调用 YY_INPUT，参考1第二章

默认 flex 生成的词法分析函数不可重入，即在没有同步的前提下不能用于多线程；可以在使用 Flex 生成 C 函数时使用 --rerntrant 命令，生成可重入的解析函数

每个 Bison 规则中的语法符号都有一个语义值，目标符号（冒号左边的语法符号）的值在动作中代码用 $$ 代替，右边语法符号的语义值依次为$1、$2 直到这条规则的结束。下表列出了一些 Bison 常见变量与函数

函数&变量 备注
%left '+' '-' / %right / %nonassoc / %prec UMINUS / 1. Bison 设置优先级，以解决部分场景的冲突
2. 其他解决优先级的方式是合理的安排规则顺序

Flex 输入文件格式为：

%{
Declarations /* 这部分内容是 C 代码，会被原样拷贝进lex.yy.c 文件中，当前内容可以没有*/
%}

Definitions  /* 定义用于下面 Rules 中的宏，当前内容可以没有 */

%%
Rules        /* 规则定义，规则必须有 */
%%

User codes   /* 用户 C 代码 */

下面是使用 flex 实现单词计数程序（wc）的示例。flex 程序（将文件保存为 fl.l）：

/* flex 程序分为三个部分，用两个百分号进行分割 */
/* 第一部分包含声明与选项设置，%{ %} 之间的内容会被原样拷贝到生成的 C 代码中 */
%{
int chars = 0;
int words = 0;
int lines = 0; 
    
int yywrap(void){ return 1; } // 加上这行可以避免链接 fl 库
%}

/* 当前 flex 文件没有使用 Definitions */

/* 左侧模式右侧行为，匹配到的字符串会保存在全局变量 yytext 中 */
/* 如果输入的字符串匹配正则表达式， 则执行右侧的 C 代码 */
/* 对于有歧义的匹配过程，flex 有两条原则：1 最大一口原则； 2 位于前面的规则优先级更高 */

%%
[a-zA-Z]+ {words++; chars += strlen(yytext);} 
\n        {chars++; lines++;} 
.         {chars++;} 
%%
/* 第三部分是 C 代码，这部分不写也是可以的，-lfl 时会自动从 fl 中引入一个主函数 */
int main(int argc, char **argv){
    yylex();
    printf("%d,%d,%d\n", lines, words, chars);
}

将 flex 程序转化为 c 代码：

flex fl.l         # 自动生成 lex.yy.c 文件

# 生成可执行文件，这里不要用 g++，因为 c/c++ 符号命名问题，使用 g++ 编译会失败
# gcc lex.yy.c -lfl # 如果 flex 文件中没有定义 yywrap 函数，需要链接 fl 库
gcc lex.yy.c      
# 执行
./a.out < fl.l

Bison

函数&变量 备注
%x COMMENTS_S 声明状态机起始状态

示例

示例可以参考这里

ANTLR 4 简介

很多语言使用 antlr 来生成编译器前端代码，antlr 相对于 flex&Bison 这类工具而言使用了更新的技术。antlr 是使用 Java 开发的，所以执行 antlr4 工具需要 java 环境，可以从这里下载 ANTLR 4.8 tool itself 。比较好的入门资料是官方文档 Getting Started wit ANTLR v4

简单示例 C++

这里摘取官方文档中 Windows 下的配置方式，我使用的 cmd 终端是 cmder，使用的命令行工具源自 git/bin，编译环境为 WSL

  1. 安装 Java 1.6 及以上版本

  2. 下载 antlr-4.7.1-complete.jar

  3. 将 antlr-4.7.1-complete.jar 加入到环境变量中

    1. 长久有效的方法是直接将路径写入到 CLASSPATH 环境变量中

    2. 临时有效：SET CLASSPATH=.;./antlr-4.7.1-complete.jar;%CLASSPATH%

      1. linux ：export CLASSPATH=".:./antlr-4.7.1-complete.jar:$CLASSPATH"

      2. 如果不想设置环境变量，那么在执行 java 命令时需要带上 jar 包的目录位置，例如

        javac -cp "./antlr-4.7.1-complete.jar" Hello*.java

  4. 执行命令：java org.antlr.v4.Tool %*，如果配置生效会输出下面内容，可以参考官方文档为命令设置别名

    ANTLR Parser Generator  Version 4.7.1
 -o ___              specify output directory where all output is generated
 -lib ___            specify location of grammars, tokens files
 -atn                generat......

hello world

定义语法规则，保存为 Hello.g4

// Define a grammar called Hello
grammar Hello;
r  : 'hello' ID ;         // match keyword hello followed by an identifier
ID : [a-z]+ ;             // match lower-case identifiers
WS : [ \t\r\n]+ -> skip ; // skip spaces, tabs, newlines

生成对应语言的解析代码

java -Dfile.encoding=UTF8 -jar antlr-4.7.1-complete.jar -Dlanguage=Cpp Hello.g4

为了更方便的使用 ANTLR，可以先生成 Java 代码，然后做一些简单的测试，下面以上面的 Hello.g4 为例介绍下 ANTLR4 的 org.antlr.v4.gui.TestRig 工具

  1. 生成 java 代码：java -Dfile.encoding=UTF8 -jar antlr-4.7.1-complete.jar Hello.g4
  2. 编译生成 class 文件：java Hello*.java
  3. 执行命令：java -cp "./antlr-4.7.1-complete.jar" org.antlr.v4.gui.TestRig Hello r -tree
    1. 输入 hello world，换行（点击 Enter 键）
    2. windows 下需要输入 CTRL+z，linux 平台下输入 CTRL+D
    3. 再次点击换行键
  4. 重复执行 3 ，不过将命令中的 -tree 改为 -gui，ANTLR 将以图形界面的形式输出语法分析树；-tree 以 Lisp 文本的形式展示
    1. 其他常用参数解释
      1. -tokens，打印词法符号流；-ps file.ps ，以 PostScript 格式保存语法分析树结果；
      2. -trace 打印规则名称及进入和离开规则时的词法符号
      3. -encoding encodingname，指定输入文件的编码
      4. -diagnostics，开启解析过程中的调试信息输出，比如定义的规则有歧义
      5. -SLL，使用另外一种更快但功能相对较弱的解析策略
ANTLR4 语法简介
  • 语法规则以小写字母开始
  • 词法规则以大写字母开始
  • 使用 | 分割一个规则的若干备选分支，例如：stat: expr NEWLINE|NEWLINE;

其他参考

书籍：自制编程语言 / 两周自制脚本语言 / Why you should not use (f)lex, yacc and bison / ANTLR 4权威指南 /

开源工具：lex/yacc、flex/bison、python PLY / ANTLR4 / Boost Spirit / lexertl / 等，细节请参考 Wikipedia

进阶学习：TCC /

  1. JohnLevine, and 莱文. flex与bison. 东南大学出版社, 2011. ↩︎

  2. Paxson, Vern, Will Estes, and John Millaway. “Lexical analysis with flex.” University of California (2023): 28. ↩︎

  3. LICENSE, GNU GENERAL PUBLIC. “Bison.” (2023). ↩︎

#lexer #词法分析 #ANTLR4 #flex #bison
Next Linux网络编程

See Also

Flex&Bison