编译原理chapter3新.pptVIP

第三章;词法分析程序与语法分析程序的接口方式 词法分析程序的输出 将词法分析工作分离的考虑;组织成语法分析程序的子程序 组织成一遍扫描。;词法分析程序的输出;词法分析器的输出常用二元式表示： （单词种别，单词自身的值） 单词的种别提供给语法分析程序使用；单词自身的属性值提供给编译其他阶段使用。对有些单词，不仅需要它的值，还需要其他一些信息以便编译的进行。比如标识符，需记载它的类别、层次等，这些若都放在符号表中，则标识符的二元式表示形式可为： （标识符，该标识符在符号表中位置的指针） ; if i=5 then x:=y; ‘if’，‘i’，‘=’，‘5’，‘then’， ‘x’， :=,‘y‘,’;’;将词法分析工作分离的考虑; 词法分析程序主要功能是识别单词，同时在扫描源程序时，还可以完成其他一些任务，比如：注释和空白处理、出错位置定位、预处理等等。;单词的描述工具;正规文法;正规式，也称为正则表达式，是表示正规集的工具，也是描述单词符号的工具。在下面的定义中，?是字母表， ?`={?,?,|,.,*,(,)}是辅助字母表。 ;注：（1）正规表达式描述的集合称作正规集（正规表达式的计算描述如何构造正规集）。（2）“*”，“.”，“?”运算左结合，优先级由高到低。 例：?=?A,B,…,Z,a,b,…,z,0,1,…,9? A ?B... ?Z ?a ?b... ?z L( A)?L( B)…L( Z) ?L( a) ?L( b)... L(z) = ?A,B,…,Z,a,b,…,z? 0 ?1 ?.. . ?9 L(0) ?L(1) ?... ?L(9)= ? 0,1,…,9?; ( A ?B... ?Z ?a ?b... ?z) (( A ?B... ?Z ?a ?b... ?z) ?(0 ?1 ?.. . ?9))* ?A,B,…,Z,a,b,…,z? (?A,B,…,Z,a,b,…,z?? ? 0,1,…,9?)* 例3.3 ?=?a,b? (a) a ?b ?a,b? (b) (a ?b )(a ?b ) ?aa,ab,ba,bb? ( c) a* ??,a,aa,aaa,aaaa,…? (d) (a ?b)* {?,a,b,aa,ab,ba,bb,aaa,... ? (e) a ?ab* {a,ab,abb,abbb,…}; 若两个正规式x和y所表示的正规集相同，则说x和y等价，写作x=y。 例： x=a|b，y=b|a,则x=y,即a|b=b|a 同样，s(rs)*=(sr)*s (r|s)*=(r*s*)*;;正闭包r+, 表达的语言 (L( r ))+ (L( r ))+=(L( r ))1? (L( r ))2 ? (L( r ))3 ?…… r*=r+??? r+= r r*;程序设计语言的单词都能用正规式来定义;正规文法到正规表达式;将?上的一个正规式转换成文法G=(VT,VN,S,P) 令其中VT= ?，确定产生式和VN的元素方法如下： 1)对任何正规式r，选择一个非终结符S生成正规式产生式S-r,并将S定为G的识别符号; 2)若x和y都是正规式,对形如A-xy的正规式产生式,重写成:A-xB B-y两产生式,其中B是新选择的非终结符,即B ∈ VN。 3）对已转换的文法中的形如A-x*y的正规式产生式，重写为：A-xB A-y B-xB B-y 其中B为一新的非终结符。 4）对形如A-x|y的正规式产生式，重写为A-x A-y。5）不断利用上述规则变换，直到每个产生式都符合正规文法的形式。;2. 将正规文法转换成正规式 这个转换过程基本上是上述过程的逆过程，最后 只剩下一个开始符号定义的产生式，并且该产生 式的右部不含非终结符。 正规文法到正规式的转换规则表： 文法产生式 正规式 规则1 A-xB B-y A=xy 规则2 A-xA|y A=x*y 规则3 A-x