自然语言的文法
<句子> -> <名词短语 > <动词短语> <名词短语> -> <形容词> <名词短语> <名词短语> -> <名词> <动词短语> -> <动词> <名词短语> <形容词> -> little <名词> -> boy <名词> -> Apple <动词> -> eat
单词串 little boy eats apple
推导
给定文法 G = (Vt, Vn, P, S),如果 a -> b ∈ P 那么可以将符号串rag 中的a换成b 也就是说 rag可以重写为rbg
记作 rag => rbg
此时称作文法符号串rag直接推导rbg
也就是用产生式的右部替换产生式的左部
如果a0 => a1, a1 => a2, a2 => a3
那么 可以记作 a0 => a1 => a2 => a3
称作a0经过3步推导出a3,可以简记为a0 =>³ a3
a =>0 a
=> + 表示经过正数步推导
=> * 表示经过若干步推导,可以是0步
我们再来看最开始那个自然语言文法
<句子> => <名词短语> <动词短语> => <形容词><名词短语><动词短语> => little <名词短语><动词短语> => little <名词> <动词短语> => little boy <动词><名词短语> => little boy eats <名词短语> => little boy eats <名词> => little boy eats apple
这种从上到下推倒下来的过程叫做推导
错从下到上推回去叫做 归约
句型
如果S =>* a, a ∈ (Vt ∪ Vn)* 则称a是G的一个句型
一个句型中即可包含终结符又可包含非终结符,也可能是空串
若 S=>* w, w ∈ Vt* 则称w是G的一个句子
句子是不高喊非终结符的句型
由文法G的开始符号S推导出的所有橘子构成的集合称为文法G生成的语言, 记为L(G)
L(G) = {w | S => * w, w ∈ Vt*}
文法 E-> E+E | E * E | (E) | id
生成的语言中包含无穷多个句子
例 : 文法G
S -> L | LT
T -> L | D | TL | TD
L -> a | b | c | … | z
D -> 0 | 1 | 2 | 3 | … | 9
则
T => TL
=> TDL
=> TDDL
=> TLDDL
=> TD…LDDL
可以无限走下去 T表示字符数字串
该文法生成的语言是标识符
