- 1、本文档共113页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
编译原理课件 三章
复习:程序语言的语法描述 几个概念: 考虑一个有穷 字母表∑ 字符集 其中每一个元素称为一个字符 ∑上的字(也叫字符串) 是指由∑中的字符所构成的一个有穷序列 不包含任何字符的序列称为空字,记为ε 用∑*表示∑上的所有字的全体,包含空字ε 复习:程序语言的语法描述 ∑*的子集U和V的连接(积)定义为 UV={ ?? | ??U ??V } V自身的 n次积记为 Vn=VV…V 规定V0={?},令 V*=V0∪V1∪V2∪V3∪… 称V*是V的闭包; 记 V+=VV* ,称V+是V的正规闭包。 复习:程序语言的语法描述 上下文无关文法的定义: 一个上下文无关文法G是一个四元式 G=(VT,VN,S,P),其中 VT:终结符集合(非空) VN:非终结符集合(非空),且VT ? VN=? S:文法的开始符号,S?VN P:产生式集合(有限),每个产生式形式为 P??, P?VN, ? ? (VT ? VN)* 开始符S至少必须在某个产生式的左部出现一次。 复习:程序语言的语法描述 定义:称?A?直接推出???,即 ?A????? 仅当A ? ?是一个产生式, 且?, ?? (VT ? VN)* 。 如果?1 ? ?2 ? ? ??n,则我们称这个序列是从?1到?n的一个推导。若存在一个从?1到?n的推导,则称?1可以推导出?n 。 通常,用 表示:从?1出发,经过一步或若干步,可以推出?n。 复习:程序语言的语法描述 最左推导:任何一步? ? ?都是对?中的最左非终结符进行替换。 最右推导:任何一步? ? ?都是对?中的最右非终结符进行替换。 复习:程序语言的语法描述 用一张图表示一个句型的推导,称为语法树。 复习:程序语言的语法描述 定义:如果一个文法存在某个句子对应两颗不同的语法树,则说这个文法是二义的。 语言的二义性:一个语言是二义性的,如果对它不存在无二义性的文法。 复习:程序语言的语法描述 形式语言鸟瞰 0型(短语文法,图灵机): 产生式形如: ? ? ? 其中:?? (VT ? VN)*且至少含有一个非终结符;?? (VT ? VN)* 1型(上下文有关文法,线性界限自动机): 产生式形如: ? ? ? 其中:|?| ? |?|,仅 S?? 例外。 复习:程序语言的语法描述 形式语言鸟瞰 2型(上下文无关文法,非确定下推自动机): 产生式形如: A ? ? 其中:A? VN;?? (VT ? VN)*。 3型(正规文法,有限自动机): 产生式形如: A ? ?B 或 A ? ? 其中: ?? VT*;A,B?VN 产生式形如: A ? B? 或 A ? ? 其中: ?? VT*;A,B?VN 第三章 词法分析 词法分析的任务:从左至右逐个字符地对源程序进行扫描,产生一个个单词符号。 词法分析器(Lexical Analyzer) 又称扫描器(Scanner):执行词法分析的程序 3.1 对于词法分析器的要求 一、词法分析器的功能和输出形式 功能:输入源程序、输出单词符号 单词符号的种类: 基本字:如 begin,repeat,? 标识符——表示各种名字:如变量名、数组名和过程名 常数:各种类型的常数 运算符:+,-,*,/,? 界符:逗号、分号、括号和空白 输出的单词符号的表示形式: (单词种别,单词自身的值) 单词种别通常用整数编码表示。 若一个种别只有一个单词符号,则种别编码就代表该单词符号。假定基本字、运算符和界符都是一符一种。 若一个种别有多个单词符号,则对于每个单词符号,给出种别编码和自身的值。 标识符单列一种;标识符自身的值表示成按机器字节划分的内部码。 常数按类型分种;常数的值则表示成标准的二进制形式。 例 C程序 while (i=j) i--; 输出单词符号: while, - (, - id, 指向i的符号表项的指针 =, - id, 指向j的符号表项的指针 ), - id, 指向i的符号表项的指针 --, - ;, - 例 FORTRAN程序 IF (5.EQ.M) GOTO 100 输出单词符号: 逻辑IF (34,-) 左括号 (2,-) 整常数 (20, ‘5’的二进制) 等号 (6,-) 标识符 (26, ‘M’) 右括号 (16,-) GOTO (30,-) 标号 (19, ‘100’的二进制) 二、词法分析器作为一个独立子程序 词法分析是作为一个独立的阶段,是否应当将其处理为一遍呢? 作为独立阶段的优点:结构简洁、清晰和条理化,有利于集中考虑词法分析一些枝节问题。
您可能关注的文档
最近下载
- 2023年齐齐哈尔体育馆坍塌事故全文课件.ppt VIP
- 班会“尊重”优秀课件.pptx
- 必威体育精装版人教版一年级上册劳动教案.docx
- 传染病报告登记本.docx VIP
- 2024陆上风力发电机组预应力预制混凝土塔筒施工与质量验收规范.pdf
- Python程序设计 第 4 章 Python 数据类型、Python程序设计 第4章 Python 数据类型.ppt
- 成人高考成考高等数学(一)(专升本)试卷及答案指导(2024年).docx VIP
- 必威体育精装版中小学教师高级职称晋升初中语文学科讲课答辩真题汇编(附答案详解).pdf
- 六年级上册美术课件-5《风景写生》 人教版(共24张PPT).pptx
- 2021年成人高考高起点地理历史试题及答案.doc VIP
文档评论(0)