编译原理第三章.ppt

1、第1，3章语法和语言，3.1语法的直观概念3.2符号和符号字符串3.3语法和语言格式定义3.4语法类型3.5上下无关语法和语法树3.6句分析3.7语法实用说明，2，3.1语法的直观概念，见下面的语法3360|我|他王|(常数)这三个符号称为元语言符号，描述语法符号之间的关系。4，终结器和终结器称为语法符号。生成式(规则)左右语法起始符号下的句子“我是大学生。”名为的生成过程：5，3.2符号和符号字符串，字母：字母表是元素的非空可怜集合。符号字符串：是由字母表中的符号组成的所有可怜序列称为符号字符串。示例：符号字符串是有序空符号字符串符号字符串的长度，6，符号字符串是：符号字符串的连接符号字符串

2、的平方，7，符号字符串集：集合a的所有元素是字母表中定义的符号字符串，则a在该字符中称为符号字符串集合。示例：符号字符串集合的乘积：是A，B是两个符号字符串的集合，而A和B的乘积ab= xy | xA，yB 示例3360，8，闭包3360定义字母表中的任意长符号字符串集合。 *标记。示例：静态闭包：=*-，9，3.3语法和语言的格式定义，将3.1语法g定义为4元组(VN，vt，p，s)。其中，VN非终结器集vt是起始符号，表示终结器集p到规则集s，必须至少在一个规则中显示为左侧部分。显然，VNvt= v=VNvt，语法g的字母。10，例如，规则：第一次生成的左侧是语法的开始符号：a，b，c，是

3、终结器a、b、c、是终止元，表示符号字符串用语法g s书写。其中s是语法的起始符号，定义11，3.2。如果 有语法G的生成式，/v，*符号，则，W满足=，W= ，W=直接生成W，W直接生成v，或者W是v= W的最左边推导，最右边推导，W如果x仅由结束符号组成，则sx，x称为GS的句型13。通过定义3.6语法g创建的语言使用集合x | sx，其中s是语法标识符，x/vt用l (g)表示该集合。如果3.7定义l (G1)=l (G2)，语法G1和语法G2是等效的。14，3.4语法类型，基于0的语法：设置g=(VN，vt，p，s)。所有结果 满意：如果有vt(VNvt)，并且至少有一个非终结符和vt

4、(VNvt)，则g是0英寸语法。1型语法。g=(VN，vt，p，s)是0型语法，p的每个生成型 是满足| |，s 唯一例外的情况下，语法g是1型语法或上下文相关语法。*，15，类型2语法：将g=(VN，vt，p，s)设置为类型1语法，p的每个结果 都满意。是非终止元，vt，语法g与类型2或上下文无关。类型3语法：将g=(VN，vt，p，s)设定为类型2语法。p的每个生成形式都是a b或a ，其中a和b给定非终结符、v语法、语句形式，就可以画出对应于该语句形式的语法树。语法树图片：1。根是语法的开始符号。2.末端从左到右连接的符号环是给定的句型。3.为内部节点或根节点a创建的aa1a2.如果有A

5、K，则a的儿子从左到右依次为a1、a2、AK。，17，示例：给定的句型SaAS，ASbA，ASS，Sa，Aba绘制与句型abbaa相对应的语法树。18、语法的量义性：一个语法树代表句型的不同诱导过程。但是一个句型是否对应唯一的语法树呢？句型中唯一的诱导最左边(最右边)吗？不是。例如：e I，e e，e e * e，e (e)句I * I最左边的推导有两个：ei * e ei * I ei * I ei * I衍生2 ee * ei * ei * e ei * I ei * I ei * I IEEE ee * eiie ei iii衍生1的语法树衍生2的语法树，语法的二义性。在编程语言中要避免

6、，但是判断一个上下文无关的语法是否是2的义的问题不能递归理解。我们能做的就是找到一套关于无义性的充分条件。例如：2的语法：语法g=(e，*，I，(，)，P，E)，其中P表示e I，e e，Et | E | E可以从左到右逐个识别输入符号，确认该符号字符串是否是给定语法的句子吗？分析方法：1。由上而下分析2。自下而上分析，21，3.6.1自上而下分析方法：在语法的起始符号中反复使用各种生产形式。查找“匹配”输入符号字符串的推导。范例：语法GSScAdAabAa输入字串w=cabd识别语法中的句子。解决方案：ScAdcabd可以知道输入符号字符串w是语法中的句子。22，3.6.2自下而上分析方法从

7、输入符号字符串开始逐步“返回”。直到回到语法的开始符号。范例：语法GSScAdAabAa输入字串w=cabd识别语法中的句子。解决方案：在SAAcabdcabdcabd中，您可以看到输入符号字符串w是该语法中的句子。、23、与句型分析相关的问题：由上而下分析方法的主要问题包括：如果要替换的最左端和右端为v，并且有n个规则，则v=a1 | a2 | | an的一个解决方案是从所有可能的选择中随机选择一个，如果以后发现这是错误的，则必须返回并再次尝试其他选择。这种方法称为回溯。在自下而上分析方法中，在分析操作的每个阶段，从当前字符串中选择子字符串，并将其分类为非结束符号。这个子字串称为可收合字串。

8、问题是如何在每个步骤中确定此“可折叠字符串”。在标准收阖分析中，此可收阖字串称为处理码。定义24，3.8的g是语法，s是语法的开始符号， 是语法g的一个句型。如果有SA和a ，那么“beta”是与非终结符a相反的语句。特别是，如果有A ，则是与文型 相反的规则a 的直球(也称为简单球)。句型最左边的直球称为这个句型的把手。在门型柔道树上很容易找到门型的球体和直球。只要a设置为门型 ，就是子树的根。其中是形成这个子树结束节点的符号字符串，其中是与a相对的门型 的短语。如果这个子树只有一层，是句型 的直接短语。*，25，3.7语法实用的一些说明，3.7.1语法的实用限制实用，我们不能在语法中包含有害规则和过剩规则1。有害规则：UU，不需要，