【编译原理】语法分析之分析策略

╰半橙微兮° 2024-03-31 14:21 90阅读 0赞

## 1. 语法分析的目的 ##

**构建一个解析树或语法树**

1.  根：独特的符号，“< program >"或其他
2.  叶子：词法分析阶段的tokens序列
3.  树中的每个分支点都由语法规则认可
4.  可能同时执行语义检查
5.  这个阶段可以一次一位地生成一系列机器代码指令或程序的其他中间形式
6.  如果程序的语法无效，请尽可能多地给出有用的错误消息

**识别比单词更大的单位**

1.  单位表示语法结构
2.  表达式、函数、声明

**基于词汇分析，根据语法规则。例如**  
A:=x + 3.14\*y

**指出语法错误**  
**生成内部表达式以便进行语义处理**

## 2. 分析树 ##

1.  根：语法起始符号
2.  内部节点：有一个或多个孩子
3.  叶子：没有孩子

## 3. 两种解析策略 ##

**搜索问题 – 给定根和叶，在它们之间找到适当的标记分支点**

**自顶向下解析策略**  
从顶部开始搜索，从< program >开始，尝试向下搜索填充在树中的树叶。

**自下而上的解析策略**  
从词汇分析阶段的叶子序列开始，在我们朝着＜program＞的方向前进时，尝试构建树的一部分。

## 4. 语法分析器 ##

语法分析器决定了程序的机构。  
语法分析的结果是**解析树**或**语法树**。

解析树:  
![在这里插入图片描述][025b487992d641258524a1897d52ba53.png]

## 5. 语法分析的两种句法分析策略 ##

**自上而下分析** LL（1）/\*\* k =1 \*\*/

1.  第一个L代表从左边开始扫描
2.  第二个L表示产生最左推导
3.  数字1表示每一步推导式只需要向后看一个符号就可以

**自下而上分析**LR（0）/\*\* k =0 \*\*/

1.  第一个L代表从左边开始扫描
2.  第二个R代表最右推导的逆过程
3.  数字0表示向右查看0个字符

**语法分析的概念**  
形式上，对于指定的字符串α，识别它是否是指定语法G(Z)的句子。

**解析策略的标准**  
力量  
回退  
预测  
效率  
小规模

**解析策略的标准-力量**  
必须足够强大，以便分析语言。

Earley和CYK可以用于任何上下文无关的语法。

当我们为新的编程语言编写语法时，我们必须检查语法是否与所提出的解析策略兼容。如果没有，我们必须以适当的方式修改语法。

**解析策略的标准-回退**  
一些解析策略涉及反向跟踪。

当解析器确定先前关于解析树某部分的形式的决定是错误的时，它会返回到该决定，并以不同的方式重新执行该决定。

反向跟踪效率很低，因为它需要解析器对输入流进行多次传递。

但该决定的任何后果也必须以某种方式扭转。

1.  从符号表中删除或修改的条目
2.  删除生成的机器/中间代码
3.  等等

一旦对输入程序的某一部分的形式做出决定，就永远不会修改。

本模块中的技术**不**需要反向跟踪。

**解析策略的标准-向前看**  
回退的另一种选择是向前看，当解析器需要做出决定时，它会查看输入流中接下来的几个标记，以帮助做出正确的决定。

原则上，解析器可以沿着输入程序任意地看得很远，也许可以一直看到底，但这可能效率很低。

我们希望尽量减少向前看。

两种策略都涉及一定的前瞻性，但它们通常需要最多一个前瞻性符号。

当做出决定时，解析器只允许查看来自词法分析器的下一个输入标记。这对于普通编程语言来说通常足够了。

**解析策略的标准-效率**  
需要与程序长度成比例的时间。

解析策略是O（n）算法，其中n是输入字符串的长度。

**解析策略的标准-小规模**  
如果解析器也可以很小，那就太好了，但现在问题不大了，因为存储非常便宜。

一些版本的最佳解析策略实际上可以生成非常大的表，以向解析器指定在每种情况下要做什么。如果我们在一台小型机器上工作，就必须避免这种情况。

**自上而下分析**  
从顶部（根）到底部（叶）构造解析树。

通常从符号S开始的过程导出字符串w。

如果每个字符串都在树叶上，那么这个句子就被接受了。

在每一步中，我们应该有两个选择：

1.  应替换哪个非终端
2.  这个非终端产品应该用哪个来替代

**两种解析策略**  
两组主要的解析策略，称为LL(K)和LR(K)

**第一个L**表示从左到右处理令牌的输入流

k是允许的前瞻tokens的数量，结果通常是0或1

**第二个**字母指定解析器生成的派生类型

LL(k)解析器产生最左边的派生，是一个自顶向下的解析器。

LR(k)解析器产生最右边的派生，是一种自下而上的方法。

LL(k)和LR(k)不像Early和CYK那样完整，但幸运的是足以处理大多数PL语法。

***Thanks to Dr. John: Some contents are from their slides.***

[025b487992d641258524a1897d52ba53.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/cf17f1da38a34e3788c276ae03ca027a.png

发表评论取消回复

表情：

评论列表（有 0 条评论，90人围观）

还没有评论，来说两句吧...

相关阅读

相关词法、语法、语义分析编译原理设计

目录 1 目的 4 2 设计思路与实现 4 2.1 编译过程概述 4 2.2 Flex与Bison工具的简介 5 2.2.1 Flex文件内容结构 5

素颜马尾好姑娘i/ 2024年04月07日 12:09/ 0 赞/ 78 阅读

相关【编译原理】语法分析之分析策略

1. 语法分析的目的构建一个解析树或语法树 1. 根：独特的符号，“< program >"或其他 2. 叶子：词法分析阶段的tokens序列 3. 树中的每个

╰半橙微兮°/ 2024年03月31日 14:21/ 0 赞/ 91 阅读

相关编译原理PL0语法分析实验1

语法分析程序与词法分析程序共同点语法分析程序又叫下推自动机，词法分析程序又叫有穷自动机。 1，待分析的简单语言的词法相同点：都是分析种别码不同点：词法分析器分

朱雀/ 2023年10月01日 08:52/ 0 赞/ 23 阅读

相关【编译原理】图灵机、词法分析和语法分析

图灵机、词法分析和语法分析图灵机词法分析 LA (scanner)的作用编辑器的作用汇编程序和编译器

小灰灰/ 2023年09月24日 17:49/ 0 赞/ 75 阅读

相关编译原理教程_4 语法分析

> 文章原稿 > https://gitee.com/fakerlove/fundamentals-of-compiling 文章目录 4. 语法分析

╰半夏微凉°/ 2023年01月21日 11:17/ 0 赞/ 260 阅读

相关编译原理语法分析（文本输入）源程序

\include<stdio.h> \include<string.h> lrparser(); yucu(); statement(); expressi

朴灿烈づ我的快乐病毒、/ 2022年08月02日 10:47/ 0 赞/ 184 阅读

相关自顶向下语法分析——编译原理

编程学习-编译原理本语法分析是编译程序的核心功能之一。语法分析的作用是识别由词法分析给出的单词符号串是否是给定问法的正确句子（程序）。语法分析常用的方法可分为自顶向

以你之姓@/ 2022年06月06日 12:06/ 0 赞/ 441 阅读

相关语法分析-哈工大编译原理实验二

实验2语法分析实验目的 1．巩固对语法分析的基本功能和原理的认识。 2．通过对语法分析表的自动生成加深语法分析表的认识。 3．理解并处理语法分析中的异常和错误

妖狐艹你老母/ 2022年06月05日 06:05/ 0 赞/ 258 阅读

相关编译原理学习（三）--语法分析树

语法分析树用图形方式展现了从文法的开始符号推导出相应语言中的符号串的过程。在具体理解语法分析树之前需要先理清楚一些基本概念： ①.产生式用变量expr来表示表达式，用变量

我就是我/ 2022年05月24日 06:57/ 0 赞/ 521 阅读

相关编译原理入门（四）——语法分析简介

编译器编译的第二步便是语法分析，废话不多说，继续看。语法分析：语法分析的主要任务是：从词法分析器输出的token序列中识别出各类短语，并

心已赠人/ 2022年05月09日 08:54/ 0 赞/ 216 阅读