《编译原理》课堂笔记(2):词法分析

词法分析概述

词法分析程序的作用:

  • 从左到右扫描构成源程序的字符流
  • 识别出有词法意义的单词(Lexemes)
  • 返回单词记录(由单词记号(Token)和单词的属性值组成),或词法错误信息
  • 次要任务:滤掉空格、跳过注释、换行符、追踪换行标志、复制出错源程序、宏展开、访问符号表……

一般都是由语法分析程序调用,基本任务都是识别单词

例:Pascal程序
position := initial + rate * 60
词法单元 单词属值
标识符 position
赋值算符(:=)
标识符 initial
加算符(+)
标识符 rate
乘算符(*)
整数常量 60
分号(;)

词法分析程序的设计与实现

常用的单词描述工具:

  • 扩展巴克斯范式(EBNF)
  • 状态转换图
  • 正规表达式
  • 有限状态自动机

实例:某语言词法分析程序的设计
单词类别(种别)的EBNF描述
<无符号整数> ::= <数字>{<数字>}
<标识符> ::= <字母>{<字母>|<数字>}
<字母> ::= a|b|…|X|Y|Z
<数字> ::= 0|1|2|…|8|9
<保留字> ::= const|var|procedur|begin|end|odd|if|then|call|while|do|read|write
<运算符> ::= +|_|*|\|=|#|<|<=|>|>=|:=
<界符> ::= (|)|,|;|.

词法单位(单词符号):
标识符1个:ident
无符号整数1个:number
保留字13个:beginsym | endsym | …
运算符11个:plus | minus | …
界符5个:lparen | rparen | …

词法规则的状态转换图:
dfa.png

技术个案

  • 如何区分标识符与保留字

预设一个保留字表,通过查表来确定是否保留字

  • 字符退还

在识别双符号运算符之类的单词时,要注意到可能需要进行字符退还

词法分析程序的自动构造

词法分析程序自动构造的典型过程

  1. 使用者用正规表达式作为词法规则的形式描述,每一类词法单元都对应一个正规表达式,所有正规表达式以文本方式作为自动构造工具的输入。
  2. 自动构造工具将每一个正规表达式转换成有限自动机的形式,比如使用Thompson构造法将正规表达式转换成ϵ-NFA
  3. (可选)增加一个新的开始状态,从该状态引一条ϵ-转移边到上述每一个ϵ-NFA的状态,得到一个新的ϵ-NFA
  4. 必要时自动构造工具会将这些ϵ-NFA确定化,比如使用子集构造法得到DFA
  5. 必要时,自动构造工具会将有限自动机最小化,得到等价拥有状态数目最小的DFA。
  6. 若执行过第3步,那么模拟单个完整的自动机;否则,自动构造工具按照一定的控制策略生成词法分析程序中扫描程序的代码,该扫描程序可以选择对每一类词法单元所对应的有限自动机依次模拟运行,并从当前输入符号序列中识别下一个单词,然后返回相应的单词记录。

直接设计正规表达式有时比较困难,可以先设计自动机,再转换成正规表达式。


新增一则回应

除非特别注明,本页内容采用以下授权方式: Creative Commons Attribution-ShareAlike 3.0 License