Безконтекстни граматики, умозаключение, ляво и дясно заключение, синтактичен анализ на дърво

Помислете за граматика, която извежда всички правилни последователности в скоби.

[math] "(" [/ math] и [math] ")" [/ math] - терминални символи [math] S [/ math] - начален нетерминал

1. [math] S \ rightarrow (S) S [/ math]
2. [math] S \ rightarrow S (S) [/ math]
3. [math] S \ rightarrow \ varepsilon [/ math]

[math] \ boldsymbol \ Rightarrow (S) \ boldsymbol \ Rightarrow (S) (\ boldsymbol) S \ Rightarrow (S) () \ boldsymbol \ Rightarrow (\ boldsymbol) () \ Rightarrow (\ boldsymbol (S)) () \ Rightarrow (S (S) (\ boldsymbol)) () \ Rightarrow (S (S) (\ boldsymbol (S))) () \ Rightarrow (S (\ boldsymbol) ((S))) () \ Rightarrow ( \ boldsymbol () ((S))) () \ Rightarrow (() ((\ boldsymbol))) () \ Rightarrow (() (())) () [/ math]

Помислете за изхода на лявата страна на скобата от примера:

[math] \ boldsymbol \ Rightarrow (\ boldsymbol) S \ Rightarrow ((\ boldsymbol) S) S \ Rightarrow (() \ boldsymbol) S \ Rightarrow (() \ boldsymbol (S)) S \ Rightarrow (() (\ boldsymbol)) S \ Rightarrow (() (\ boldsymbol (S))) S \ Rightarrow (() ((\ boldsymbol))) S \ Rightarrow (() (())) \ boldsymbol \ Rightarrow (() (( ))) (\ boldsymbol) S \ Rightarrow (() (())) () \ boldsymbol \ Rightarrow (() (())) () [/ math]

Нека да изградим синтактично дърво за синтактична скоба от примера.

Използване на индукция върху височината на дървото.

Основа: Основата е височината [math] 1 [/ math], най-малката възможна за синтактично дърво с терминална корона.

Тъй като това дърво е синтактично дърво, [math] A \ rightarrow \ omega [/ math] трябва да бъде продукция. По този начин, [math] A \ Rightarrow_ \ omega [/ math] е едноетапно ляво поколение на [math] \ omega [/ math] от [math] A [/ math] .

Индукционна връзка: Има корен, маркиран с [math] A [/ math] и синове, маркирани отляво надясно [math] X_1X_2 \ dots X_k [/ math]. [Math] X [/ math] символите могат да бъдат както терминали, така и променливи.

1. Ако [math] X_i [/ ​​math] е терминал, тогава дефинираме [math] \ omega_i [/ ​​math] като верига, състояща се от един [math] X_i [/ ​​math] .
2. Ако [math] X_i [/ ​​math] е променлива, тогава тя трябва да бъде коренът на някакво поддърво с терминална корона, което ние обозначаваме с [math] \ omega_i [/ ​​math]. Имайте предвид, че в този случай височината на поддървото е по-малка от [math] n [/ math], така че хипотезата за индукция се отнася за него. Следователно има ляв хайвер [math] X_i \ Rightarrow ^ _ \ omega_i [/ ​​math] .

Имайте предвид, че [math] \ omega = \ omega_1 \ omega_2 \ dots \ omega_k [/ math]. Нека да конструираме лявото поколение на веригата [math] \ omega [/ math], както следва:

Нека започнем със стъпка [math] A \ Rightarrow_ X_1X_2 \ dots X_k [/ math]. След това за [math] i = 1, 2, \ dots, k [/ math] показваме, че се извършва следното поколение: [math] A \ Rightarrow ^ _ \ omega_1 \ omega_2 \ dots \ omega_iX_X_ \ dots X_k [/ математика]

Това доказателство всъщност използва друга индукция, този път на [math] i [/ math]. За основа [math] i = 0 [/ math] вече знаем, че [math] A \ Rightarrow_ X_1X_2 \ dots X_k [/ math] .

За индукция, да предположим, че съществува следният продукт: [math] A \ Rightarrow ^ _ \ omega_1 \ omega_2 \ dots \ omega_X_iX_ \ dots X_k [/ math]

1. Ако [math] X_i [/ ​​math] е терминал, тогава не правим нищо, но в следващото разглеждаме [math] X_i [/ ​​math] като терминална верига [math] \ omega_i [/ ​​math ]. Така стигаме до съществуването на следващото поколение. [math] A \ Rightarrow ^ _ \ omega_1 \ omega_2 \ dots \ omega_iX_X_ \ dots X_k [/ math]
2. Ако [math] X_i [/ ​​math] е променлива, тогава ние продължаваме, като генерираме [math] \ omega_i [/ ​​math] от [math] X_i [/ ​​math] в контекста на вече изграденото поколение . По този начин, ако това производство е: [math] X_i \ Rightarrow_ \ alpha_1 \ Rightarrow_ \ alpha_2 \ dots \ Rightarrow_ \ omega_i [/ ​​math], след това продължете със следните поколения:

---