3.6.2 Viable Prefixes慕课视频播放-Compilers Techniques-MOOC慕课视频教程-柠檬大学

各位同学大家好

这节课我们来学习语法分析中活前缀的概念

活前缀

我们首先学习一下它的定义

我们观察到

右句型的活前缀

是指这个前缀它不超过最右句柄的右端

那么首先我们要知道

右句型是使我们在进行推导的时候

进行最右推导所形成的句型

那么前缀的意思是指

一个符号串的前缀

从第一个符号开始连续的若干个符号构成的一个子串

我们把它用数学的形式来表示出来

假设从S开始进行最右推导

我们得到了γAω

然后在下一步

我们仍然进行最右推导

假设ω全部都是终结符的串

那么我们需要推导的A

假设存在着A产生β这样的产生式

我们将A推导为β

也就是在下一步

我们得到了γβω

在这种情况下，β是句柄

那么γβ的任何前缀

它都是一个活前缀

因为β是句柄

我们只要不超过 β 的最右端

它都是我们所认为的活前缀

也就是包括空串、γβ本身以及γ本身都是活前缀

如果参照活前缀的定义的话

我们根据一个具体的例子来讲一下

到底哪些符号是活前缀呢？

仍然是用文法S产生aABe

A产生Abc或者b

B产生d

我们只要知道哪些是句柄

只要在自下而上的分析中

我们把句柄分析出来

然后每一次我们找出来

所有不超过句柄最右端的那些前缀

就是我们所要的活前缀

我们先看一下

自下而上的分析中

可能出现的一些串

包括

a、ab、aA、aAb、aAbc、aAd、

aAB、aABe以及S

我们知道这些符号

是在自下而上的分析中

在栈中可能出现的一些串

我们再继续分析一下

有如下的几个情况

首先如果一个活禽缀

已经包含了这个句柄的全部的符号

那么我们应该想到

句柄整个出现了

它在活前缀中

最终整个句柄都出现了

如果这样的话

我们应该参照它对应的产生式

来进行归约

比如说ab

它已经出现在栈里边

我们观察到b是一个句柄

如果b是句柄

我们需要按照A产生b这个产生式来进行归约

再比如说栈里边的aAbc

如果是串的话

我们仍然发现是已经出现了句柄

A可以产生Abc

那么需要按照产生式来进行归约

还有aAd

这个时候d作为句柄出现

我们需要将 d 归约为B

接下来的一个串aABe

我们可以认为

它已经出现了整个句柄

我们需要将它归为S

接下来我们来看一下第2个情况

在栈里边没有出现整个句柄

而是出现了句柄的一部分

比如说我们有一个产生式

A可以产生β1β2

在栈里边β1已经出现了

接下来我们期待的是β2的出现

我们来看一下

这种情况的例子

比如说栈中出现了一个串aA

我们发现其实没有形成句柄

但是根据产生式A可以产生Abc

我们期待在A之后能看到b和c

再比如说

栈中如果出现了aAb

我们接下来希望看到的是c

如果栈中出现的串aAB

我们接下来期待出现的是e

第3个情况

活前缀当中不含有任何的符号

在这种情况下

我们期望着可以通过产生式A产生β的右部

所推导出来的符号

我们也就是期待着β的出现

比如说第1个情况

栈里边是a这个符号

我们接下来期待A的出现

而A不会出现在输入串中

它是由归约得到的

这一小节就到这

谢谢大家

Compilers Techniques课程列表：

1 Overview of Compilers Techniques

-1.1 Overview of Compilers Techniques

--Chapter 1 Overview of Compilers Techniques

--Overview of Compilers Techniques

2 Lexical Analysis

-2.1 Lexical Tokens, Strings and Language

--2.1 Lexical Tokens, Strings and Language

-2.2 Regular form

--2.2 Regular form

-2.3 Finite automata

--2.3 Finite automata

-2.4 DFA construction, Subset construction, Simpleset DFA

--2.4 DFA construction, Subset construction, Simpleset DFA

-2.5 Lex

--2.5 Lex

3 Syntax Analysis

-3.1 Context-free Grammars

--3.1.1 The Role of the Parser

--3.1.2 The Formal Definition of a Context-free Grammar

--3.1.3 Derivations

--3.1.4 Ambiguity

-3.2 Writing a Grammar

--3.2.1 Elimination of Left Recursion

--3.2.2 Left Factoring

--3.2 Top-Down Parsing

-3.3 Languages and Grammars

--3.3 Languages and Grammars

--3.3 Language and Grammars

-3.4 Top-Down Parsing

--3.4.1 First and Follow

--3.4.2 LL(1) Grammers

--3.4.3 Recursive Descent Analysis

--3.4.4 Nonrecursive Descent Analysis

-3.5 Bottom-up Parsing

--3.5.1 Reductions and Handle

--3.5.2 Shift- Reduce Parsing

--Bottom-up Parsing

-3.6 LR Parsing

--3.6.1 LR Parsing

--3.6.2 Viable Prefixes

--3.6.3 Simple LR

--3.6.4 LR(1)

--3.6.5 LALR

--3.6.6 Characteristics of LR Parsing

--3.6.7 Non Ambiguous and Not LR Context-Free Grammars

4 Syntax-Directed Translation

-4.1 Syntax-Directed Definitions

--4.1.1 Attribute Grammars

--4.1.2 Attribute Dependency Graphs and Ordering the Evaluation of Attributes

--Syntax-Directed Definitions

-4.2 Bottom-Up Calculation of S Attribute

--4.2.1 Bottom-Up Calculation of S-Attributed

--4.2.2 Stack Code

-4.3 L-Attributed Definitions

--4.3.1 L-Attributed Definitions

--4.3.2 Translation Schemes

--4.3.3 Design of Predictive Translator

--L-Attributed Definitions

-4.4 Bottom-Up Parsing of L-Attributed Translation

--4.4.1 Bottom-Up Parsing of L-Attributed Translation

--4.4.2 Simulate the Parsing of Inherited Properties

--Bottom-Up Parsing of L-Attributed Translation

5 Organization and Management of Run-Time Storage Space

-5.1 Overview

--5.1 Overview

--Overview

-5.2 Global Stack Storage

--5.2 Global Stack Storage

-5.3 Calling Sequences

--5.3 Calling Sequences

-5.4 Non Local Names

--5.4 Non Local Names and dynamic scope

--Non Local Name

6 Intermediate Code Generation

-6.1 Overview of Intermediate Code Generation

--6.1 Overview of Intermediate Code Generation

-6.2 Declaration Statements

--6.2 Declaration Statements

7 Code Generation

-7.1 Issues in the Design of Code Generator

--7.1 Issues in the Design of Code Generator

-7.2 Target Machine

--7.2 Target Machine

--Target Machine

-7.3 Basic Blocks and Flow Graphs

--7.3 Basic Blocks and Flow Graphs

-7.4 A Simple Code Generator

--7.4 A Simple Code Generator

8 Design and Implementation of a Simple Compiler

-8.1 Demonstration of Compiler Framework based on Python

--8.1 Demonstration of Compiler Framework based on Python

-8.2 Basic

--8.2.1 Scanner

--8.2.2 Parser -1LRItem

--8.2.3 Parser-2ActionGoto

--8.2.4 SA

-8.3 SimpleJava

--8.3 SimpleJava

3.6.2 Viable Prefixes在线视频

3.6.2 Viable Prefixes课程教案、知识点、字幕