ZČU
Syntaktická analýza algoritmem Cocke-YOUNGER-KASAMI (CYK)
Zadání
Napište program, který bude provádět syntaktickou analýzu řetězců pomocí algoritmu Cocke-Younger-Kasami (CYK).
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
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
!!! Pozor !!! Nezapomeňte na to, že CYK vyžaduje gramatiku v Chomského normální formě. Váš program nemusí vstupní gramatiku do této formy převádět, ale MUSÍ zjistit, zda gramatika v Chomského normální formě je či není a případně zareagovat varovnou hláškou.
Příklad gramatiky2. 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:
