文法 ●本书特指上下文无关文法( Context free grammar, CFG ●程序设计语言中往往存在嵌套结构 ●上下文无关文法是一种能够很好描述程序设计语言的 表示方法 stmt if expr ) stmt else stmt expr Stmt→
文法 本书特指上下文无关文法（Context Free Grammar, CFG） 程序设计语言中往往存在嵌套结构 上下文无关文法是一种能够很好描述程序设计语言的 表示方法 stmt → if ( expr ) stmt else stmt expr → …… stmt → …… 6
CFG的定义 一个CFG由以下几个部分构成 终结符号 组成串的基本符号,与“词法单元名字”同义 ·非终结符号 语法变量,表示特定串的集合 给出了语言的层次结构,这种层次结构是语法分析和翻译的关键 个开始符号 某个特定的非终结符号,其表示的串集合是这个文法生成的语言 一组产生式 描述将终结符合和非终结符号组合成串的方法 产生式左部(头)是一个非终结符号 符号“→” 个由零个或多个终结符号与非终结符号组成的产生式右部(体)
CFG的定义 一个CFG由以下几个部分构成 终结符号 组成串的基本符号，与“词法单元名字”同义 非终结符号 语法变量，表示特定串的集合 给出了语言的层次结构，这种层次结构是语法分析和翻译的关键 一个开始符号 某个特定的非终结符号，其表示的串集合是这个文法生成的语言 一组产生式 描述将终结符合和非终结符号组合成串的方法 产生式左部（头）是一个非终结符号 符号 “→” 一个由零个或多个终结符号与非终结符号组成的产生式右部（体） 7
用于描述算术表达式的文法定义 S-> NP VP VP->VNP epression erpression term NP-> NAME expression expression- term NP->ART N e pression→term NAME-> John term→term* factor V->ate term term/factor ART-> the N-> cat term actor actoN expression factor→id
用于描述算术表达式的文法定义 8 S -> NP VP VP -> V NP NP -> NAME NP -> ART N NAME -> John V -> ate ART -> the N -> cat
符号表示约定 终结符号:ab+3id 非终结符号:ABC.,S,stmt 文法符号:XY E→→E+T|E-T|T 终结符号串:vw T→T*F|T/F|F 文法符号串:aβ F→(E)lid ●不同可选体:a,a,a ●开始符号:S
符号表示约定 终结符号：a b + 3 id… 非终结符号: A B C…, S, stmt 文法符号: X Y … 终结符号串:u v w… 文法符号串:α β… 不同可选体: α1 α2 α3… 开始符号: S 9
推导 ●产生式又可称为重写规则( Rewriting rule ●从开始符号出发,每个重写步骤把一个非终结符号替换为 它的某个产生式的体。 eg.E→E→-(E)→-(id),称为从E到-(id)的推导。 这个推导说明了-(id是表达式E的一个实例,或者说由E产 ●推导的一般性定义: 假设一个产生式A→y,aAβ→aβ,符号→ 表示“通过一步推导出
推导 产生式又可称为重写规则（Rewriting rule） 从开始符号出发，每个重写步骤把一个非终结符号替换为 它的某个产生式的体。 e.g. E -E –(E) –(id) ， 称为从E到-(id)的推导。 这个推导说明了–(id)是表达式E的一个实例，或者说由E产 生。 推导的一般性定义： 假设一个产生式A→ γ，αAβ αγβ ，符号 表示“通过一步推导出”。 10