ZČU
Syntaktická analýza ZDOLA NAHORU
Zadání
Napište program, který bude provádět syntaktickou analýzu řetězců metodou zdola nahoru s backtrackingem.
Vstup programu:
1. Gramatika ve formátu grm:
; středník značí začátek komentáře
VN=ABCD ;neterminální symboly
VT=abcd ;terminální
symboly
S=A ;počáteční symbol gramatiky, pokud se nerovná přímo S (nepovinné)
P=2 ;počet pravidel gramatiky
X-AB ;pravidla, symbol -> je nahrazen pomlčkou
X-cD
Příklad gramatiky
2. Analyzovaný řetězec
IN=abcd ;vstupní řetězec
TREE=13 ;počet řádek stromu
S ;vlastní derivační strom - úrovně odděleny TABELÁTOREM, který je zde nahrazen znakem „-“
- X
- - A
- - - a
- - - b
- - c
- Y
- - B
- - - B
- - - - d
- - - c
- - C
- - - e
Výše uvedený příklad tedy odpovídá tomuto derivačnímu stromu:
S=A ;počáteční symbol gramatiky, pokud se nerovná přímo S (nepovinné)
P=2 ;počet pravidel gramatiky
X-AB ;pravidla, symbol -> je nahrazen pomlčkou
X-cD
Příklad gramatiky
2. Analyzovaný řetězec
Výstup programu
1. Rozhodnutí o přijetí/odmítnutí řetězce
2. VŠECHNY MOŽNÉ derivační stromy řetězce v dané gramatice v tomto formátu (.dtr):
GRM=xxxx.grm ;soubor s gramatikouIN=abcd ;vstupní řetězec
TREE=13 ;počet řádek stromu
S ;vlastní derivační strom - úrovně odděleny TABELÁTOREM, který je zde nahrazen znakem „-“
- X
- - A
- - - a
- - - b
- - c
- Y
- - B
- - - B
- - - - d
- - - c
- - C
- - - e
Výše uvedený příklad tedy odpovídá tomuto derivačnímu stromu:
