编译原理第三章词法分析解析
- 格式：ppt
- 大小：3.25 MB
- 文档页数：45
下载文档原格式
合集下载
《编译原理》第3章
NFA到相应的DFA的构造的基本思路是： DFA的每 一个状态对应NFA的一组状态. DFA使用它的状 态去记录在NFA读入一个输入符号后可能达到的 所有状态.
NFA M所能接受的符号串的全体记为L(M)
结论：
上一个符号串集V是正规的，当且仅当存 在一个上的不确定的有穷自动机M，使得 V=L(M)。
DFA是NFA的特例.对每个NFA N一定存在一个DFA Ｍ，使得 L(M)=L(N)。对每个NFA N存在着与之 等价的DFA M。 有一种算法，将NFA转换成接受同样语言的DFA.这 种算法称为子集法. 与某一NFA等价的DFA不唯一.
0
1
S P
Z
{P} {}
{P}
{S,Z} {Z}
{P}
• δ为S * 到S的子集(2 S)的一种映射
• 从NFA的矩阵表示中可以看出，表项通常是一状态的集合， 而在DFA的矩阵表示中，表项是一个状态
∑*上的符号串t被NFA M接受:
• 对于Σ*中的任何一个串t，若存在一条从某一初态 结点到某一终态结点的道路，且这条道路上所有 弧的标记字依序连接成的串(不理采那些标记为ε 的弧)等于t，则称t可为NFA M所识别(读出或接 受)。 • 若M的某些结点既是初态结点又是终态结点；或 者存在一条从某个初态结点到某个终态结点的道 路,其上所有弧的标记均为ε，那么空字ε可为M所 接受。
其中： δ(S，0)={P}
δ(S，1)={S，Z} δ(Z，0)={P} δ(Z，1)={P} δ(P，1)={Z} • 状态图表示
1 1 S 0 0,1 Z
P
1
• 矩阵表示
状态 输入
δ(S，0)={P} δ(S，1)={S，Z} δ(Z，0)={P} δ(Z，1)={P} δ(P，1)={Z}
北航编译原理课件 03.词法分析
3. 词法分析程序算法
北京航空航天大学计算机学院
17
1.单词及内部表示 单词及内部表示: 单词及内部表示
单词名称
BEGIN END FOR DO IF THEN ELSE 标识符 常数(整 常数 整) : + * , ( ) :=
保留字和分界符采用一符一类
记忆符
BEGINSY ENDSY FORSY DOSY IFSY THENSY ELSESY IDSY INTSY COLONSY PLUSSY STARSY COMSY LPARSY RPARSY ASSIGNSY
字母、数字
标识符 无符号整数
单字符分界符
S S S
字母
标 数字
非字母数字
出口
数字
数
非数字
出口
+ * ， 单界 （ ） ：
其他字符 非=
出口
双字符分界符
北京航空航天大学计算机学院
S
冒号
=
双界
其他字符
出口 15
查保留字表 读字符
字母、数字
S
字母
标 数字
非字母数字
标识符
非数字
数字
数
无符号整数 单字符分界符
如：b{ab} = {ba}b {a|b} = {{a} {b}} = (a*b*)*
北京航空航天大学计算机学院 23
例：设 ∑ = { a,b },下面是定义在∑上的正则表达式和正则集合 正则表达式 ba* a(a|b)* (a|b)*(aa|bb)(a|b)* 正则集合
北京航空航天大学计算机学院
北京航空航天大学计算机学院 20
‘*’ : ‘,’ : ‘(’ : ‘)’ : ‘:’ :
编译原理词法分析及词法分析程序
∴M能识别出L(G)中的全部句子。
状态图=>右线性文法
文法G[0] 0->a1
d 0
S->aA A->dA A->b
a c
1 2
b
d
3
1->d1 1->b
0->c
0->c2 2->d
S->c
S->cB，2有出弧 B->d
左线性文法=>状态转换图
设G=(VN,VT,P,S)是一左线性文法,令|VN|=K， 1) 则所要构造的状态转换图共有K+1个状态. 2) VN中的每个符号分别表示K个状态 2.1) G的开始符S为终止状态 3) 起始状态,用R(VN)标记
识别符号串与归约
S
从初态R到下一状态A对应Ba，即终结 符a归约成非终结符B; U 从状态B转换到状态A对应ABa,即将 Ba归约为A; 状态A转换到状态S(终态)对应S Aa,即 U 将Aa归约为开始符S. 归约成功,恰好进入终态,即状态转换图识 U 别了(或接受)该符号串. 识别00011的例子的归约过程
f是转换函数，是在K×Σ →K上的映像，即：如果f（ki，a）=kj， （ki，kj∈K）意味着，当前状态为ki，输入字符为a时，将转换 为下一个状态kj，我们把kj称作ki的一个后继状态；
1.确定的有限自动机
通常把这五要素组成的五元式M=(K,∑,f, S0,Z)称为确定的 有限自动机(DFA)，它是相应的状态转化图的一种形式描 述，或者说，是状态转换矩阵的另一种表示。 在状态转换的每一步，据DFA当前所处状态及扫视的输入 字符，能唯一确定下一状态。
例：文法G=({S,U},{0,1},{SS1 |U1,
状态图=>右线性文法
文法G[0] 0->a1
d 0
S->aA A->dA A->b
a c
1 2
b
d
3
1->d1 1->b
0->c
0->c2 2->d
S->c
S->cB，2有出弧 B->d
左线性文法=>状态转换图
设G=(VN,VT,P,S)是一左线性文法,令|VN|=K， 1) 则所要构造的状态转换图共有K+1个状态. 2) VN中的每个符号分别表示K个状态 2.1) G的开始符S为终止状态 3) 起始状态,用R(VN)标记
识别符号串与归约
S
从初态R到下一状态A对应Ba，即终结 符a归约成非终结符B; U 从状态B转换到状态A对应ABa,即将 Ba归约为A; 状态A转换到状态S(终态)对应S Aa,即 U 将Aa归约为开始符S. 归约成功,恰好进入终态,即状态转换图识 U 别了(或接受)该符号串. 识别00011的例子的归约过程
f是转换函数，是在K×Σ →K上的映像，即：如果f（ki，a）=kj， （ki，kj∈K）意味着，当前状态为ki，输入字符为a时，将转换 为下一个状态kj，我们把kj称作ki的一个后继状态；
1.确定的有限自动机
通常把这五要素组成的五元式M=(K,∑,f, S0,Z)称为确定的 有限自动机(DFA)，它是相应的状态转化图的一种形式描 述，或者说，是状态转换矩阵的另一种表示。 在状态转换的每一步，据DFA当前所处状态及扫视的输入 字符，能唯一确定下一状态。
例：文法G=({S,U},{0,1},{SS1 |U1,
编译原理词法分析
❖ 数字：继续读，直到非数字字符出现或文件尾。输 出无符号整数的单词记号及数字串；
❖ =、＜、＞、！：读下一个字符，判断是否为双字 符分界符，若是，组成双字符分界符，输出类码； 若不是，输出单分界符记号；
编译原理
❖ 非=、＜、＞、/等与双分界符首字符不同的单分界 字符：输出相应单词记号及单分界符。
1.S是一个有穷集，它的每个元素称为一个状态；
2.Σ是一个有穷字母表，它的每个元素称为一个输入 符号，所以也称Σ为输入符号表；
3.δ是在S×Σ→S上的单值映射，即，如δ (s，a)=s’， (s∈S，s’∈S)就意味着，当前状态为s，输入符为 a时，将转换为下一个状态s’，我们把s’称作s的一 个后继状态；
编译原理 在 入 准初带备整•••始的读输读有个时开入始入头穷模，始，状带：控型读位状态：可制由头置态存以器如状的所三处，处放在：果态符识部于表于输输控读正号别分输示初入入制头好组组符带状移是成成号上态动终的：向发到结字后生最状能移变后态被头每有动化一，该转向读穷个则有移后入控符输限到移一 制号入自下动个器后带动一一符控面上机个个号制，状位，状态置读态，
编译原理
词法分析 读字符
结束 Y
结束
N Y 空字
N 字母 N 数字
Y 组合标识符 Y 组合整数
查保留字Βιβλιοθήκη N 纯单分符Y 输出单分符
N
>,<,!,= Y 读字符
=
N
N
/ Y 读字符
*
N
Y
错误处理
输出保留字
Y 保留字
N 输出标识符
组合整数
读字符
Y 输出双分符
输出单分符 N 输出单分符/
注释处理
读字符
❖ =、＜、＞、！：读下一个字符，判断是否为双字 符分界符，若是，组成双字符分界符，输出类码； 若不是，输出单分界符记号；
编译原理
❖ 非=、＜、＞、/等与双分界符首字符不同的单分界 字符：输出相应单词记号及单分界符。
1.S是一个有穷集，它的每个元素称为一个状态；
2.Σ是一个有穷字母表，它的每个元素称为一个输入 符号，所以也称Σ为输入符号表；
3.δ是在S×Σ→S上的单值映射，即，如δ (s，a)=s’， (s∈S，s’∈S)就意味着，当前状态为s，输入符为 a时，将转换为下一个状态s’，我们把s’称作s的一 个后继状态；
编译原理 在 入 准初带备整•••始的读输读有个时开入始入头穷模，始，状带：控型读位状态：可制由头置态存以器如状的所三处，处放在：果态符识部于表于输输控读正号别分输示初入入制头好组组符带状移是成成号上态动终的：向发到结字后生最状能移变后态被头每有动化一，该转向读穷个则有移后入控符输限到移一 制号入自下动个器后带动一一符控面上机个个号制，状位，状态置读态，
编译原理
词法分析 读字符
结束 Y
结束
N Y 空字
N 字母 N 数字
Y 组合标识符 Y 组合整数
查保留字Βιβλιοθήκη N 纯单分符Y 输出单分符
N
>,<,!,= Y 读字符
=
N
N
/ Y 读字符
*
N
Y
错误处理
输出保留字
Y 保留字
N 输出标识符
组合整数
读字符
Y 输出双分符
输出单分符 N 输出单分符/
注释处理
读字符
03-第3章-语法分析-编译原理-中国科技大学(共13讲)
VT : VN : S: P : 终结符集合 非终结符集合 开始符号，非终结符中的一个 产生式集合， 产生式形式 : A expr (expr) expr id op
• 例 ( {id, +, , , (, )}, {expr, op}, expr, P )
expr expr op expr expr expr op +
3.2 语言和文法
• 无二义的文法 stmt matched _stmt | unmatched_stmt matched_stmt if expr then matched_stmt else matched_stmt | other unmatched_stmt if expr then stmt | if expr then matched_stmt else unmatched_stmt
3.2 语言和文法
expr expr + term | term term term factor | factor factor id | (expr)
expr term
term expr factor id term factor id expr + term * factor id id + id id 分析树
3.2 语言和文法
3.2.3 验证文法产生的语言 G : S (S) S | L(G) = 配对的括号串的集合 • 按串长进行归纳：配对括号串可由S推出
–归纳基础： S – 归纳假设：长度小于2n的都可以从S推导出来 – 归纳步骤：考虑长度为2n(n 1)的w = (x) y S (S)S * (x) S * (x) y
编译原理和技术
中国科学技术大学 计算机科学与技术学院 陈意云
• 例 ( {id, +, , , (, )}, {expr, op}, expr, P )
expr expr op expr expr expr op +
3.2 语言和文法
• 无二义的文法 stmt matched _stmt | unmatched_stmt matched_stmt if expr then matched_stmt else matched_stmt | other unmatched_stmt if expr then stmt | if expr then matched_stmt else unmatched_stmt
3.2 语言和文法
expr expr + term | term term term factor | factor factor id | (expr)
expr term
term expr factor id term factor id expr + term * factor id id + id id 分析树
3.2 语言和文法
3.2.3 验证文法产生的语言 G : S (S) S | L(G) = 配对的括号串的集合 • 按串长进行归纳：配对括号串可由S推出
–归纳基础： S – 归纳假设：长度小于2n的都可以从S推导出来 – 归纳步骤：考虑长度为2n(n 1)的w = (x) y S (S)S * (x) S * (x) y
编译原理和技术
中国科学技术大学 计算机科学与技术学院 陈意云
编译原理第三章练习题答案
编译原理第三章练习题答案编译原理第三章练习题答案编译原理是计算机科学中的重要课程之一，它研究的是将高级语言程序转化为机器语言的过程。
在编译原理的学习过程中，练习题是提高理解和应用能力的重要途径。
本文将为大家提供编译原理第三章的练习题答案，希望能够对大家的学习有所帮助。
1. 什么是词法分析？请简要描述词法分析的过程。
词法分析是编译过程中的第一个阶段，它的主要任务是将源程序中的字符序列划分为有意义的词素（token）序列。
词法分析的过程包括以下几个步骤：1）扫描：从源程序中读取字符序列，并将其转化为内部表示形式。
2）识别：根据预先定义的词法规则，将字符序列划分为不同的词素。
3）分类：将识别出的词素进行分类，如关键字、标识符、常量等。
4）输出：将分类后的词素输出给语法分析器进行进一步处理。
2. 什么是正则表达式？请给出一个简单的正则表达式示例。
正则表达式是一种用于描述字符串模式的工具，它由一系列字符和操作符组成。
正则表达式可以用于词法分析中的词法规则定义。
以下是一个简单的正则表达式示例：[a-z]+该正则表达式表示匹配一个或多个小写字母。
3. 请简要描述DFA和NFA的区别。
DFA（Deterministic Finite Automaton）和NFA（Nondeterministic Finite Automaton）是有限状态自动机的两种形式。
它们在词法分析中常用于构建词法分析器。
DFA是一种确定性有限状态自动机，它的状态转换是确定的，每个输入符号只能对应一个状态转换。
相比之下，NFA是一种非确定性有限状态自动机，它的状态转换是非确定的，每个输入符号可以对应多个状态转换。
4. 请简要描述词法分析器的实现过程。
词法分析器的实现过程包括以下几个步骤：1）定义词法规则：根据编程语言的语法规范，定义词法规则，如关键字、标识符、常量等。
2）构建正则表达式：根据词法规则，使用正则表达式描述不同类型的词素。
3）构建有限状态自动机：根据正则表达式，构建DFA或NFA来识别词素。
词法分析-编译原理-03-(二)
5. 5.1 5.2 5.3 5.4 5.5 5.6 5.7 6 6.1 6.2
isalpha(ch) : ch→buf; 下一字符→ch WHILE isalpha(ch) OR isdigit(ch) DO ch→buf; 下一字符→ch 回送 ch; key = isKeyword(buf) IF key >= 0 THEN 返回 key Lookup( buf ) → attr 返回 IDN ':' : 下一字符→ch; IF ch等于'=' THEN 返回 ASG 出错处理
第三章 词法分析 3.1 词法分析的任务
输入源程序，输出单词符号
把构成源程序的字符串转换成语义
上关联的单词符号的序列
单词符号
token
按照最小的语义单位设计， 通常表示为二元组
（单词种别，属性值）
1) 单词符号的表示
单词种别
通常按照语法分析的需要设置． 常用： 各关键字，标识符，常数，各
例3-3 状态图的实现算法
1. 2. 3.1 3. 4. 4.1 4.2 4.3 4.4 4.5 读入当前字符 ch //跳过空格 WHILE ch 是空格 DO 下一字符 → ch CASE ch OF isdigit(ch) : ch→buf; 下一字符→ch WHILE isdigit(ch) DO ch→buf; 下一字符→ch 回送 ch 将缓冲区的数字字符串变成数字→attr 返回 NUM
7 8 9 10 11 12 13 14 15 16 17 18
'+' : 返回 ADD '-' : 返回 SUB '*' : 返回 MUL '/' : 返回 DIV '=' : 返回 EQ '>' : 返回 GT '<' : 返回 LT '(' : 返回 LP ')' : 返回 RP ';' : 返回 SEMI 其它 : 出错处理 END OF CASE
哈工大编译原理.ppt
procedure SORT(CH);
{ case CH of ‘字母’:
‘字母’: call RECOGID(CH,TOKEN);
‘/’: call HANDLECOM(CH,TOKEN);
‘数字’: call RECOGDIG(CH,TOKEN);
‘’‘
call RECOGSTR(CH,TOKEN);
if TOKEN!=‘ ’ then call PRINTERR(‘注解未完’);
TOKEN:=‘ ';
return }
25
识别界限符(RECOGDEL) 输入：CH内含单界限符； 输出：各种界符的TOKEN字; procedure RECOGDEL(CH,TOKEN); { case CH of
otherwise call RECOGDEL(CH,TOKEN);
end case;
write TOKEN into TOKEN文件;
Return } 23
procedure RECOGID(CH,TOKEN);
{ WORD:= ‘ ’; WORD:=WORD||CH; Repeat {
call GETCH(CH);
%%
标识符 {入口地址=LOOKUP();}
%%
LOOKUP()
31
辅助过程是动作需要的，这些过程用C书 写，可以分别编译.例：LOOKUP()
32
28
声明 %% 翻译规则 %% 辅助过程
29
声明包括变量，符号常量和正规定义式。
翻译规则的形式为：
p1
{ 动作1}
p2
{ 动作2}
…
…
pn
{ 动作n}
30
每个pi是正规定义式的名子，每个{动 作i}是正规定义式pi识别某类单词时，词 法分析器应执行动作的程序段。用C书 写。
编译原理中的词法分析与语法分析原理解析
编译原理中的词法分析与语法分析原理解析编译原理是计算机科学中的重要课程，它研究的是如何将源程序翻译成目标程序的过程。
而词法分析和语法分析则是编译过程中的两个重要阶段，它们负责将源程序转换成抽象语法树，为接下来的语义分析和代码生成阶段做准备。
本文将从词法分析和语法分析的原理、方法和实现技术角度进行详细解析，以期对读者有所帮助。
一、词法分析的原理1.词法分析的定义词法分析（Lexical Analysis）是编译过程中的第一个阶段，它负责将源程序中的字符流转换成标记流的过程。
源程序中的字符流是没有结构的，而编程语言是有一定结构的，因此需要通过词法分析将源程序中的字符流转换成有意义的标记流，以便之后的语法分析和语义分析的进行。
在词法分析的过程中，会将源程序中的字符划分成一系列的标记（Token），每个标记都包含了一定的语义信息，比如关键字、标识符、常量等等。
2.词法分析的原理词法分析的原理主要是通过有限状态自动机（Finite State Automaton，FSA）来实现的。
有限状态自动机是一个数学模型，它描述了一个自动机可以处于的所有可能的状态以及状态之间的转移关系。
在词法分析过程中，会将源程序中的字符逐个读取，并根据当前的状态和字符的输入来确定下一个状态。
最终，当字符读取完毕时，自动机会处于某一状态，这个状态就代表了当前的标记。
3.词法分析的实现技术词法分析的实现技术主要有两种，一种是手工实现，另一种是使用词法分析器生成工具。
手工实现词法分析器的过程通常需要编写一系列的正则表达式来描述不同类型的标记，并通过有限状态自动机来实现这些正则表达式的匹配过程。
这个过程需要大量的人力和时间，而且容易出错。
而使用词法分析器生成工具则可以自动生成词法分析器的代码，开发者只需要定义好源程序中的各种标记，然后通过这些工具自动生成对应的词法分析器。
常见的词法分析器生成工具有Lex和Flex等。
二、语法分析的原理1.语法分析的定义语法分析（Syntax Analysis）是编译过程中的第二个阶段，它负责将词法分析得到的标记流转换成抽象语法树的过程。
编译原理第3章. 词法分析
§3.1 词法分析程序的输入输出
一.输入：字符串表示的源程序 二.输出：单词符号或单词符号表示的源程序 1.语言的单词符号：是指语言中具有独立意义的最 小语法单位。共分五类： 保留字、标识符、常数、运算符、和界符 2.单词符号的内部表示： 二元组（单词种别码，单词自身值） 继续
2019/2/25 3
6
§3.2 词法分析程序的设计 一.输入、预处理
源程序 输入缓冲区
预处理 子程序
扫描缓冲区
词法分析的预处理程序：从源 程序中处理出一串确定长度的 输入字符，并将其装进词法分 析程序的扫描缓冲区。 处理： ①删除注解、空格、回车符、 换行符之类非必要信息。 ②把标识符登录入符号表以及 某些预加工处理等。
2019/2/25 11
2.由正规文法构造状态转换图
(1).右线性文法 => 状态转换图
已知: G=(VN , VT , P , S ) P : A→aB | a A , B∈VN , a∈VT* 求: 状态转换图M 设: | VN |=k , 则状态转换图M共有k+1个结点 方法: ①初态=S , 增设终态结点F ②对G中形如A→aB 的产生式, 从结点A引一条矢 线到结点B , 并用 a 标记。 ③对G中形如A→a 的产生式, 从结点A引一条矢 线到终态结点F , 并用 a 标记。 ④对G中形如A→ε 的产生式, 从结点A引一条矢 线到终态结点F , 并标记为 ε , 或令A为接受状态。
第三章. 词法分析§3.0 词法分析程序的功能
回忆：词法分析程序的功能：对构成源程序的字符 串从左到右进行扫描和分解，并根据语言的词法 规则识别出一个个具有独立意义的单词符号。 具体： ①设计成单独一遍扫描。
源程序 词 法 分 析 单词符号序列 语 法 分 析
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
（30，_）
采用一符一种的编码方式。
（19，‘100’的二进制表示）1内0部0为的标值号用，10种0别的编二码进制19表，示单。词
例：下述C++代码段：while ( i >= j ) i - -； 经词法分析器处理以后，它将被转换为如下的单词符号串
( while ，_ ) ( ( ，_ ) ( id ，指向i的符号表指针 ) ( >= ，_ ) ( id ，指向j的符号表指针 ) ( ) ，_ ) ( id ，指向i的符号表指针 ) ( - - ，_ ) ( ； ，_ )
3、常数：常数的类型一般有整型、实型、布尔型、文字型 等。它是不限的。
4、运算符：如+、-、*、/ 等。它是确定的。
5、界符：如逗号、分号、括号、/*，*/ 等。它是确定的。
单词符号的表示形式：词法分析器所输出的单词符号常常表示成 二元式（单词种别，单词自身的值）。
单词种别可以用以下形式表示：
1、一类单词统一用一个整数值代表其属性。例如：1代表关键字， 2代表标识符等。
例如：在标准FORTRAN中 1、DO99K = 1,10 2、IF(5.EQ.M)I = 10 3、DO99K = 1.10 4、IF(5) = 55
其中的DO、 IF为关键字
其中的DO、 IF为标识符 的一部分
标识符的识别
多数语言的标识符是字母开头的“字母/数字”串， 而且在程序中标识符的出现后都跟着算符或界符。因此， 不难识别。
（2，_）
用一符一种的编码方式。
（20，‘5’的二进制表示）
常数类型，种别编码20，单词自 身等的号值为为运‘算5符’，的种二别进编制码表6示，。
（6，_）
M采为用标一识符符一，种种的别编编码码方26式，。单
（26，‘M’）
词自身值为‘M’。
（16，_）
‘)’为界符，种别编码16， 采 GO用TO一为符关一键种字的，编种码别编方码式。30，
2、每一个单词一个类别。例如：1代表BEGIN，2代表END等。
单词自身的值可以表示成：常量的二进制表示；常量、变量等在符号表 种的地址码，等等。
注意：一个语言的单词符号如何分种，分几种，怎样编码，是一个技术
问题。标识符一般同归为一种。常数则宜按类型（整、实、布尔）分。 关键字可以将其全体视为一种，也可一字一种。运算符可采用一符一种， 但也可把具有一定共性的视为一种。界符则一般采用一符一种。如何进 行分种主要取决于处理上的方便。
1、把词法分析从语法分析中脱离出来的优点： •使编译程序的结构更外加存简洁、清晰和条理化。
•词法分析和语法分析方法不同，词法分析可以使用正则文法自动构造
s•有ca利nn于er提简高单语语。法法分源程序析的效单词符号率s。canner
源程序
•可以改善词分法分析析的细节，甚至于一个语法分析配几个scanner，把不同
词法分析的任务：
从左至右逐个字符地扫描源程序，产生 一个个的单词符号，把作为字符串的源程序 改造成为单词符号串的中间程序。
词法分析器/扫描器：执行词法分析的程序。
词法分析器的功能如下图所示：
源 程
扫描器
序 scanner
1、关键字 2、标识符 3、常数 4、运算符 5、界符
由程序语言定义的具有固定意 义的标识符。也可称为保留字 或 用基来本表示字各。种例名如字：，Pa如sc变al量中名的、 b数e组gi名n，、e过nd程，名if等等。。它是不限 常 的数 。的类型一般有整型、实型、 布尔型、文字型等。它是不限 的。 运算符：如+、-、*、/ 等。 它是确定的。 界符：如逗号、分号、括号、 /*，*/ 等。它是确定的。
状态转换图的功能:用于识别一定的字符串。
初态：一张转换图的启动条件，至少有一个,用圆圈表示。
终态：一张转换图的结束条件，至少有一个，用双圈表示。
* ：表示多读进了一个字符。
词法分析器的功能：输入源程序，输出单词符号。 单词符号：一个程序语言的基本语法符号。分为以下5种。
1、关键字：由程序语言定义的具有保留字或基本字。例如：Pascal中的begin，
end，if等。它是确定的。
2、标识符：用来表示各种名字，如变量名、数组名、过程
不限
名等。它是不限的。
若是一符一种分种，单词自身值就不需要了。否则，要查符号表。
例：151－FORTRAN编译程序的词法分析器在扫描输入串 IF (5·EQ·M) GOTO 100 后，它输出的单词符号串是：
逻辑IF 左括号 整常数 等号 标识符 右括号 GOTO 标号
（34，_）
IF为关键字，种别编码34， ‘采(用’一为符界一符种，的种编别码编方码式2，。采
• 采用两个指示器：起点指示器、搜索指示器。 • 两个互补区。
TO 100 IF (5I.FE(Q5.E.MQ.M) )GGOO
TO 100
IF (5.EQ.M) GO
起点指示器 搜索指起示点器指示器 搜索指示器
搜索指示器
输输入入缓缓冲冲区区
120个字符
起点指示器
两 个互补输入缓冲区
单词符号识别的简单方法：超前搜索。 关键字识别：
的输入变成一种内部表示。
2、把词法分析作为独立的一遍
•scanner当作一遍s。csancnaenrner作为子语法程分序析
•把scanner当作子程序。
scanner作为一遍
设计前提：
输入
•
预处理
把scanner输作入为缓一冲个区独立的列子表程序；
预 处
• 词法分析器的任务为输出单词符号。
理
子程序
常数的识别
对于某些语言的常数的识别也需要使用超前搜索。
算符和界符的识别
对于诸如C++语言中的“+ +”、“- -”，这种复 合成的算符，需要超前搜索。
转换图：是一张有限方向图。在状态转换图中，结点代表 状态，用圆圈表示。状态之间用箭弧连接。箭弧上 的标记（字符）代表在射出结状态下可能出现的输 入字符或字符类。
部
扫描缓冲区
分
•必要性：编辑性字符如空白符、回车符等，除了出现在文字和
扫描常器数中以外，在别处出现都没有意义。
扫
单词符号
•功 能： 剔除无用字符。
描
语法分析器
器
•实 现： 预处理子程序。 图2.1 词法分析器
若识扫别描输缓入冲语区句的结IF构(5：.EQ.M) GOTO 100，若缓冲区情况如下所示： • 缓冲区大小：120个字符。