上下文无关文法

作者: 猫咪不吃鱼 | 来源:发表于2021-07-01 13:55 被阅读0次

CFG转CNF（附代码）
上下文无关语言
JavaScript
上下文无关文法
上下文无关文法
自然语言处理——3.5 形式语言与自动机习题
编译原理之美阅读笔记
下推自动机
软考-程序语言基础知识（上）
编译原理——语法制导翻译1.1

前言

在研究自然语言时，人们发现名词、动词、介词以及它们的短语之间存在着自然的递归关系，因此引入了 上下文无关文法(CFG) 来帮助整理和理解这种关系。同时，上下文无关文法在程序设计语言的规范化及编译中有重要应用。设计人员在编写程序设计语言的编译器和解释器时，通常需要先获取该语言的文法，因此在大多数的编译器和解释器中都包含了一个 语法分析器 。与上下文无关文法相关的语言集合称为 上下文无关语言(CFL)。

上下文无关语法概述

给出一个上下文无关语法的示例，称其为 $G_1$ :
$A \to 0A1 \\ A \to B \\ B \to \#$

一个文法是由一组 替换规则 或称 产生式 组成；每条规则占一行，由一个符号和一个字符串构成，中间用箭头隔开；符号称为变元，字符串则由变元和另一种称为 终结符 的符号构成，通常第一条规则的左边的变元被指定为 起始变元 ；则文法 $G_1$ 有3条规则， $A$ 和 $B$ 是变元，其中 $A$ 是起始变元， $0,1$ 和 $\#$ 是终结符；

按照以下方法，能够根据文法生成其所描述的语言的每一个字符串：

写下起始变元
取一个已写下的变元，并找到该变元开始的规则，把这个变元替换成规则右边的字符串
重复步骤2，直到写下的字符串中没有变元为止

例如，文法 $G_1$ 生成的字符串 $000\#111$ 。获取一个字符串的替换序列称为派生；文法 $G_1$ 生成字符串 $000\#111$ 的派生过程如下：

$A \Rightarrow 0A1 \Rightarrow 000A111 \Rightarrow 000B111 \Rightarrow 000\#111$

用上述方式生成的所有字符串构成该 文法的语言；用 $L(G_1)$ 表示文法 $G_1$ 的语言，可以得出 $L(G_1) =$ { $0^n\#1^n | n \geqslant 0$ }，该语言称为 上下文无关语言 ；通常对于 $A \to 0A1$ 和 $A \to B$ 可以合并为 $A \to 0A1 | B$

上下文无关文法形式化定义

$G = (V,\Sigma,R,S)$

$V:$ 有穷变元集
$\Sigma:$ 有穷 终结符 集
$R:$ 有穷规则集（形如 $A \to w,w \in (V \cup \Sigma)^*$ ）
$S \in V:$ 初始变元

设 $u,v$ 和 $w$ 是由变元及终结符构成的字符串， $A \to w$ 是文法的一条规则，称 $uAv$ 生成 $uwv$ ，记作 $uAv \Rightarrow uwv$ 。如果 $u = v$ ，或者存在序列 $u_1,u_2...u_k$ ，使得
$u \Rightarrow u_1 \Rightarrow u_2 \Rightarrow ... \Rightarrow u_k \Rightarrow v$
其中 $k \geqslant 0$ ，则称 $u$ 派生 $v$ ，记作 $u \overset{*}{\Rightarrow} v$ 。该语言的文法是 { $w \in \Sigma^* | S \overset{*}{\Rightarrow} w$ }；

CFG转CNF（附代码）
定理3.6 任一上下下文无关文法都可以用乔姆斯基范式的上下文无关文法产生。证明思路能够把任一上下文无关文法G转...
上下文无关语言
上下文无关文法能够描述某些具有递归结构的特征。上下文无关文法的应用：研究人类语言。在名词、动词、介词以及他们的...
JavaScript
语言按语法分类中文英文形式语言(乔姆斯基谱系)0型无限制文法1型上下文相关文法2型上下文无关文法3型...
上下文无关文法
原文地址文法：它描述语言语法结构的一组形式规则。上下文无关文法：它定义的语法范畴（或语法单位）是完全独立于这...
上下文无关文法
前言在研究自然语言时，人们发现名词、动词、介词以及它们的短语之间存在着自然的递归关系，因此引入了上下文无关文法...
自然语言处理——3.5 形式语言与自动机习题
3-1. 构造上下文无关文法用以产生：(a) 有相同数目的和的所有符号串。(b) 。 3-2. 有以下文法：其...
编译原理之美阅读笔记
03 | 语法分析（一）：纯手工打造公式计算器正则文法匹配就是key-value匹配。上下文无关文法就是二叉树的...
下推自动机
前言在证明一个语言是上下文无关的时候，有两种选择：可以给出生成它的上下文无关文法，或者给出识别它的下推自动机(...
软考-程序语言基础知识（上）
1、简单算术表达式的结构可以用下面的上下文无关文法进行描述(E为开始符号)，________是符合该文法的句子。E...
编译原理——语法制导翻译1.1
语法制导定义语法制导定义是对上下文无关文法的推广，其中每个文法符号都有一个相关的属性集。属性分为俩个子集，分别为...