学习编译原理Time05 ~ 文法的认知-技术圈

首先举个自然语言的例子，来了解句子的构成规则。

<句子> → <名词短语><动词短语>

<名词短语>→<形容词><名词短语>

<名词短语>→<名词>

<动词短语>→<动词><名词短语>

<形容词>→big

<名词>→boy

<名词>→apple

<动词>→eat

上面未用尖括号括起来部分表示语言的基本符号

尖括号括起来部分称为语法成分

文法的形式化定义

G=（V_T，V_N，P，S）

V_T：终结符集合

终结符(terminal symbol)是文法所定义的语言的基本符号，有时也称为token。

例：V_T={apple, boy, eat,big }

V_N：非终结符集合

非终结符集合(nonterminal)是用来表示语法成分的符号，有时也称为”语法变量”

例：V_N={<句子>，<名词短语>，<动词短语>，<名词>，...}

在这个要注意一下，V_T和V_N这两个集合是不相交的。V_T和V_N并起来统称文法符号集

P：产生试集合

产生式（production）描述了将终结符和非终结符组合成串的方法，一般形式为：α →β，读作α定义为β。

α(V_T U V_N)⁺, 且α中至少包含V_N中的一个元素：称为产生式的头(head)或左部(leftside)

V_T、V_N 两个字母表并起来也是一个字母表，上一篇文章也说到，字母表的闭包是是这个字母表的字符串构成的集合，因此α和β为文法符号串。

β(V_T U V_N)^*: 称为产生式的体(body)或右部(right side)

例：P={<句子> → <名词短语><动词短语>，

<名词短语>→<形容词><名词短语>，

......

}

S：开始符号

SV_N ，开始符号(start symbol)表示的是该文法中最大的语法成分。

例：S=<句子>

下面来看一下文法的例子

G=（{id，+，*，(, ) }，{E}，P，E）

P={E→E+E,

E→E*E,

E→(E),

E→id }

产生式的简写

对一组由相同左部的α产生式

α →β₁，α →β₂，...，α →β_n

可以简记为：α →β₁| β₂ |...| β_n。

读作：α定义为β₁，....,或者β_n

β₁，β₂，...，β_n称为α 的候选式(Candidate)

例：

E→E+E,

E→E*E,

E→(E),

E→id

→

E→E+E | E*E | (E) | id

为了说明哪些是终结符，哪些是非终结符，这里进行符号约定

下面符号是终结符：

字母表中排在前面的小写字母，如a，b，c
运算符，如+、*等
标点符号，如逗号，括号等
数字0，1，2、...、9
粗体字符串，如id，if等

下面符号是非终结符：

字母表中排在前面的大写字母，如A，B，C
字母S。通常表示开始符号
小写、斜体的名字，如expr、stmt等
代表程序构造的大写字母。如E(表达式)、T(项)和F(因子)

字母表中排在后面的大写字母(如X、Y、Z）

表示文法符号（即终结符或非终结符）

字母表中排在后面的小写字母(主要是u、v、...、z）

表示终结符号串（包括空串）

小写希腊字母，如α 、β、γ，表示文法符号串（包括空串）

除非特别说明，第一个产生式的左部就是开始符号

记录

点点滴滴的笔记

欢迎关注，共同学习

小浩笔记