上下文无关文法
上下文无关文法 G 是一个四元组 G = (VN , VT , S, ￡)， 其中
VN ：非终结符的非空有限集合
VT ：终结符的非空有限集合， VN ∩ VT = Φ
S： 开始符号，且S∈ VN
￡ ：形式为 P→α的产生式的有限集合， 且 P∈VN ，α∈ (VN∪VT )*
文法组成
上下文无关文法由一组终结字符，一组非终结字符，一个开始字符，一组产生式组成
终结符号：描述单词符号，组成语言的基本符号，是一个 语言的不可再分的基本符号。
非终结符：代表语法范畴，一个非终结符代表一个一定的 语法概念，每个非终结符表示一定符号串的集合。
开始符号，一个特殊的非终结符号。
产生式：又叫产生规则或规则 ，是定义语法范畴的一种 书写规则． 形式如：A→α
示例
语法规则 ：
以这句The grey will eat wolf goat.为例 (红色代表开始符号，蓝色代表非终结符号，橙色代表终结符号)
<句子>—>
<主语>
<谓语>
<主语>—>
<冠词>
<形容词>
<名词>
<谓语>—>
<动词>
<直接宾语>
<动词>—>
<助动词>
<动词原形>
<直接宾语>—>
<冠词>
<名词>
<冠词>—>The
<形容词>—>grey
<助动词>—>will
<动词原形>—>eat
<名词>—>wolf
<名词>—>goat产生式是指任意一行推导的式子
示例中可以看出非终结符都在箭头的左侧，终结符都在箭头的右侧，所以很好区分非终结符和终结符，非终结符是能够继续再分的符号串的集合，而终结符不可再分。可以这样记，产生式左侧的符号一定是非终结符，因为都能推导出新的单词符号，终结符因为不能继续推导，所以只能出现在产生式的右侧，而产生式的右侧可能是终结符也可能是非终结符，开始符是非终结符的一个特例，只能在文法中出现一次。
以上就是本人的理解，如有错误，欢迎指正！
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/214991.html原文链接：https://javaforall.net
