Kontrolltöö 1.12 (näidisülesanded)

Töös esinevad järgmist liiki ülesanded:

grammatika (kontekstivaba) koostamine ja selle ühesuse kontroll;
LLk tingimuste kontroll; LLk grammatika analüüsiks magasinmäluga automaadi juhtimistabeli koostamine;
eelnevussuhete arvutamine; eelnevusgrammatika põhjal analüüsi/redutseerimise demonstreerimine;
attribuutide abil antud käsu või programmilõigu transleerimisel saadava väljundteksti leidmine
Flex+Bison-i abil mingi osalise translaatori koostamine ja silumine (arvutil).

Järgnevates näidisülesannetes kandiliste sulgude [] vahel olev osa võib olla, aga võib ka puududa (s.t. võib esineda 0 või 1 korda), figuursulgude { } vahel olev osa aga võib esineda 0, 1, 2, ... korda (s.t. figuursulud tähistavad iteratsiooni * ). Esitatud on töös esineda võivate ülesannete tüübid (töös võib olla ülesandid vähem).

Ülesanne 1.

Kas järgmine lõik ADA manuaali grammatikast on ühene (põhjendada!):
index_constraint ( discrete_range {,discrete_range})
discrete_range subtype_indication | range
range attribute | simple_expr .. simple_expr
subtype_indication type_name [constraint]
type_name name
attribute name
constraint RANGE range

Kui see grammatika on mitmene, siis teisendada üheseks.

Ülesanne 2.

Kas grammatika

S a A | b B
A 0 A | 1
B 0 B | 1

sobib kiireks
a) ülalt-alla
b) alt-üles
analüüsiks (põhjendada) ?

Ülesanne 3.

Kas grammatika

S aAaa | bAba
A b |
on LL(k) grammatika mingi k korral; kui on, siis millise k korral (minimaalne väärtus)? Kui see ei ole LL(1), siis teisendada ta ekvivalentseks LL(1) grammatikaks.

Ülesanne 4.

Koostada LL(1) grammatika avaldiste kirjeldamiseks, kui avaldises võib kasutada täisarve, aritmeetilisi operatsioone +, -, *, / ja sulge ( ), [ ]; sulge ei või esineda rohkem kui kahel tasandis ja sellisel juhul esimesed (sisemised) sulud peavad olema ( ), välimise tasandi sulud aga [ ], s.t. on lubatud ...[..(..)..].., kuid ei ole lubatud (..(..)..), [..(..(..)..)..] jne; sulud võivad avaldises ka puududa.

Ülesanne 5.

Leida hulgad FIRST₂(S), FIRST₂(A), koostada derivatsioonipuu ja märkida tippude tekkimise järjekord LL(2) grammatika

S abA | baA |
A Saa | b

abil sõna abbabaa ülalt-alla analüüsides.

Ülesanne 6.

Koostada attribuutgrammatika until-lause analüüsiks, kui until-lause struktuur oleks
1) WHILE tingimus DO laused ENDWHILE
2) DO laused UNTIL tingimus ENDUNTIL

Ülesanne 7.

Koostada abstraktse süntaksi puu ja leida attribuutide abil (näidata igas tipus attribuutide väärtused) väljundtekst (assembler ´a la loengus 25):

WHILE
(A > B) AND (C < D) DO
UNTIL Aru > Jama DO
X := 2*A+B;
X := 2*A-B
ENDUNTIL
IF Ary<Jama
GOTO GetExmat
ELSE GoLibrary
ENDWHILE

Ülesanne 8.

Koostada Flex+Bison-i abil:
1) kompleksarvudega arvutamise kalkulaator (+,-,*,/, sulud, programm väljastab iga rea lõpus sisestatud avaldise väärtuse);
2) if-then lauseid (ilma omistamiseta) lubav täis- ja reaalarvudega arvutav kalkulaator, millele võib näiteks sisestada:

if 22*13/16>11 then 61.5/12 else 12*(34+120/3.14)