说明:双击或选中下面任意单词,将显示该词的音标、读音、翻译等;选中中文或多个词,将显示翻译。
您的位置:首页 -> 词典 -> 同步上下文无关文法
1)  synchronous context free grammars
同步上下文无关文法
2)  context free grammar
上下文无关文法
1.
, IEC61970 and IEC61980, the descriptions of their models and the context free grammar corresponding to model transduction specifications are respectively given, thus the formalization of model description is implemented.
文章针对电力系统2个重要的建模标准IEC 61970和IEC 61850,分别给出其模型表示和模型交换规范相应的上下文无关文法,实现了模型描述的形式化。
2.
Test adequacy criterion of context free grammar was formally defined and a family of grammar testing criteria was proposed.
形式化地定义了上下文无关文法的测试充分性准则 ,提出了一个上下文无关文法的测试充分性准则族 。
3.
After improving context free grammar, we develop the indeterminate syntax from the semantic information extracted from the analyzed part.
对上下文无关文法作了改进,改进后的方法能在语法分析的过程中利用已分析部分的语义信息,得出待分析部分未确定的语法结构,使其可用于处理复杂的半结构化数据。
3)  context-free grammar
上下文无关文法
1.
A method of judging similarity and equivalence in context-free grammar;
对上下文无关文法中的非终止符的相似性和等价性的判定
2.
The parallel conversion of special context-free grammars to FA;
特殊的上下文无关文法与有限自动机转换的并行处理
3.
It is proved constructly that there is a polynomial algorithm which,given a context-free grammar G and a string x,decides whether x∈L(G).
在形式语言中通过Chomsky范式“标准化”上下文无关文法,从而构造性地证明了:给定一上下文无关文法G=(V,∑,R,S)和一字符串x,必存在多项式算法确定是否x∈L(G)。
4)  context-free grammars
上下文无关文法
1.
All kinds of arithmetic based on the theory of context-free grammars is mature,how to analyze simple nominal phrase using arithmetic based on context-free grammars in self-feeding back NLU.
上下文无关文法理论成熟,以及基于其的各种算法也比较成熟。
5)  PCFG
概率上下文无关文法
1.
On the basis of the formalizable characteristic of music rhythm,a probabilistic context free grammar(PCFG) system was defined to describe the relatively independent music rhythm elements.
基于音乐节奏本身具有可被形式化的特性,定义了一个概率上下文无关文法(PCFG)系统来描述相对独立的音乐节奏元素。
6)  Commutative context-free grammar
可交换上下文无关文法
补充资料:上下文无关文法
      形式语言理论中一种重要的变换文法,用来描述上下文无关语言,在乔姆斯基分层中称为2型文法。由于程序设计语言的语法基本上都是上下文无关文法,因此应用十分广泛。
  
  范式  上下文无关文法可以化为两种简单的范式之一,即任一上下文无关语言可用如下两种标准文法的任意一种生成:其一是乔姆斯基范式,它的产生式均取A→BC或A→α的形式;其二是格拉巴赫范式,它的产生式均取A→aBC或A→α的形式。其中A,B,C∈V,是非终结符,a∈Σ,是终结符;α∈Σ*,是终结符串。
  
  同态映射下的性质  对任意正整数 n,令...,an},Σ'n={a'1,...,a'n},定义乔姆斯基变换文法G=(Σ,V,S,P)为(Σn∪Σ'n,S,S,P={S→,S→SaiSa'iS|1≤i≤n})。这个文法生成的语言称为代克集。如果把ai看作开括号,把a'i看作相应的闭括号,则n维代克集Dn就是由几种不同的括号对组成的配对序列之集合。例如,a1a2a2a'2a2a'1和a1a'1a2a'2a1a'1都属于D2,用括号表示时可以写成(〔( )〕)和( )〔 〕( )。
  
  代克集是把正则语言族扩大成上下文无关语言族的工具。对任一上下文无关语言L,必存在两个同态映射h1和h2,以及一个正则语言R,使L=h2[h1-1(D2)∩R],其中D2是二维代克集,反之亦然。
  
  更进一步,上下文无关语言族是包含D2,且在同态、逆同态和与正则语言相交三种代数运算下封闭的最小语言族。加上乘积和乘幂闭包两种运算后,此结论仍真。
  
  文法形式和文法的相似性  在两种符号置换的意义下(终结符和非终结符分别替换), 许多文法之间有着相似性。把一组彼此相似的文法抽象成一个更高级的形式体系,就叫作文法形式。迄今,文法形式的研究主要集中在上下文无关文法上。
  
  文法形式的具体定义是:给定无限的终结符表Σ和无限的非终结符表V。任取Σ和V的非空子集Σ和V,按构造普通文法的方法定义一个四元组G=(Σ,V,S,P)。在G确定以后,任取映射函数ψ,把Σ中每一元素a映为Σ中一有限子集ψ(a),把V中每一元素A映为V中一个有限子集ψ(A),且当A厵B时有ψ(A)∩ψ(B)=φ。ψ就是所需的置换。通过它得到一个具体文法ψ(G)=[ψ(Σ),ψ(V),ψ(S),ψ(P)],其中ψ(P)是把P中所有产生式中的符号作ψ置换后得到的一组新产生式,ψ(Σ),ψ(V)和ψ(S)分别是ψ(P)中出现的终结符集,非终结符集和出发符号。
  
  这样的G称为文法形式,ψ称为G 的一个解释,ψ(G)是G的一个解释文法,被认为是相似于G。令ψ遍历各种可能的解释,得到的ψ(G)集合称为G的文法性语言族,由此生成的语言集合(ψ(G))称为G的文法性语言族。例如,文法形式{S→aS,S→a}的文法性语言族是正则语言集;{S→SS,S→a}的文法性语言族是上下文无关语言集。
  
  若文法形式G作为普通文法时生成的语言(G)是无限集,则称G为非平凡的。此时文法性语言族(G)是一个满主半AFL,反之不然。如满主半AFL({anbn│n≥1}),不是一个文法性语言族。
  
  以1·2表文法性语言族12的乘积,12表两者之并,它们仍是文法性语言族。当吇12时,必有吇1或吇2成立,则称是素的。正则语言集和线性语言集都是素文法性语言族。任一文法性语言族必可唯一地分解为它的素因子乘积和:=(11...1n1)∪...∪(...mnm)。其中每个ij都是素因子。这个分解在乘积运算∪可交换的意义下是唯一的。
  
  文法的二义性  从文法生成语言,可有多种推导公式。例如文法{S→AB,A→a,B→b}可有两种推导:S崊AB崊aB崊ab及S崊AB崊Ab崊ab。若每次都取最左边的非终结符进行推导,如上例中的前一种方式那样,则称为左推导。如果有两种不同的左推导推出同一结果,则称此文法是二义性的,反之是无二义文法。对有些二义性文法,可找到一个等价的无二义文法,生成同一个语言。不具有无二义文法的语言称为本质二义性语言。例如,{S→A,S→a,A→a}是二义性文法。
  
  是本质二义性语言。
  
  子文法类  可以根据不同的观点取上下文无关文法的子文法。一种观点是根据文法的外形和它们生成的语言族在代数运算下的封闭性。例如,若文法G 的产生式只具有下列三种形式之一:A→αBβ,C→γ和S →δ,其中A,B,C∈V,αβγ∈Σ*,δ∈(Σ∪V)*,且δ中至多含k个非终结符,S是出发符号,则称G为k线性文法。1线性文法又称线性文法。全体 k线性文法之集合称为元线性文法。元线性语言族在联合和乘积运算下是封闭的,但在求交,求补,乘幂闭包和置换等运算下都不封闭。从包含关系说,正则语言族真包含于线性语言族。对任一k≥1,k线性语言族真包含于k+1线性语言族,元线性语言族真包含于上下文无关语言族。
  
  由于上下文无关文法被广泛地应用于描述计算机语言的语法,因此更重要的是从机械执行语法分解的角度取上下文无关文法的子文法,最重要的一类就是无二义的上下文无关文法,因为无二义性对于计算机语言的语法分解至为重要。在无二义的上下文无关文法中最重要的子类是LR(k)文法,它只要求向前看k个符号即能作正确的自左至右语法分解。LR(k)文法能描述所有的确定型上下文无关语言。
  

说明:补充资料仅用于学习参考,请勿用于其它任何用途。
参考词条