第四章、语法分析 Syntax analysis.pdf

第四章语法分析 陈陈 林林 提纲提纲 语法分析器语法分析器 上下文无关文法 语法分析技术语法分析技术 自顶向下 自底向上自底向上 语法分析器生成工具 描述 解析 引言引言 程序设计语言源程序的程序设计语言源程序的构成构成：：语法结构语法结构 引言引言 文法文法：：一种用于描述程序设计语言语法的表示方法种用于描述程序设计语言语法的表示方法， 能够自然地描述程序设计语言构造的层次化语法结 构构 文法给出了一个程序设计语言的精确易懂的语法规约 可以基于文法构造语法分析器可以基于文法构造语法分析器，，帮助确定源程序的语帮助确定源程序的语 法结构 语法结构有助于把源程序翻译为正确的目标代码 文法的扩展性，有助于迭代的语言演化 语法分析器语法分析器 输入输入：：词法分析器输出的词法单元序列词法分析器输出的词法单元序列 输出：语法树表示 语法分析器功能语法分析器功能： 验证输入源程序的合法性，输出良构程序的语法结构 对于病构的程序对于病构的程序，能够报告语法错误能够报告语法错误，进行错误恢复进行错误恢复 语法分析器的类型： 从左到右扫描字符 通用型通用型 自顶向下：通常处理LL文法 自底向上自底向上：通常处理通常处理LRLR文法文法 语法分析器语法分析器 类型检查，语义分析，翻译生成中间代码等往往和语法分析 过程交错完成，实践中往往和语法分析放入一个模块，图上 用“前端的其余部分”表示上述活动 代表性文法代表性文法 LR文法类 自底向上分析 无左递归 自顶向下分析自顶向下分析 上下文无关文法上下文无关文法 上下文无关文法上下文无关文法 （（ContextContext FreeFree GrammarGrammar, CFGCFG ）） 上下文无关文法是上下文无关文法是一种能够很好描述程序设计语言种能够很好描述程序设计语言 的表示方法 sttmtt → ifif (( exp r )) sttmtt ellse sttmtt expr → …… stmt → …… SinceSince thethe timetime ofof PāPāṇṇiniini, atat leastleast, linguistslinguists have described the grammars of languages in terms of their block structure, and described how sentences are recursively built up from smaller phrases, and eventually individual wordswords oror wordword elementselements. AnAn essentialessential property of these block structures is that loggical units never overlapp John, whose blue car was in the garage, walked to the green store. (J(Johhn, ((((whhose blblue car)) ((was (i(in thhe garage)))))), (walked (to (the green store)))). 上下文无关文法的定义上下文无关文法的定义 一个个CFGCFG 由以下几个部分构成由以下几个部分构成 终结符号 组成串的基本符号，与“词法单元名字”同义