Teh­tä­vä:
Backus–Naur Form

Täs­sä teh­tä­väs­sä tu­tus­tu­taan BNF:ään eli Backus-Naur-formiin. Se on erit­täin laa­jas­ti käy­tet­ty kei­no mää­ri­tel­lä oh­jel­moin­ti­kiel­ten kie­li­opil­li­sia ra­ken­tei­ta. Ma­te­ma­tii­kas­sa sa­ma asia tun­ne­taan ni­mel­lä yh­teys­riip­pu­ma­ton kie­li­op­pi (eng­lan­nik­si context-free grammar) eli CFG.

John Backus ja Peter Naur toi­vat BNF:n oh­jel­moin­ti­kiel­ten suun­nit­te­luun vuo­den 1960 mo­lem­min puo­lin. He ei­vät kui­ten­kaan ol­leet sen kek­si­jöi­tä. Var­hai­sin tun­net­tu olen­nai­ses­ti sa­man idean käyt­tä­jä oli Pāṇini, jo­ka käyt­ti si­tä sanskrii­tin kie­len ra­ken­tei­den esit­tä­mi­seen yli 2400 vuot­ta sit­ten. Sii­tä, et­tä hän ei saa­nut ni­meään maail­man­luo­kan huip­pu­kek­sin­töön­sä, hän saa syyt­tää vain tu­los­pis­te­ty­pe­ryyt­tään: mi­täs jät­ti tu­lok­sen­sa jul­kai­se­mat­ta vi­ral­li­ses­ti tu­los­pis­te­ser­ti­fioi­duis­sa tie­de­leh­dis­sä.

Täs­sä vai­hees­sa on tär­keää tun­nis­taa ja erot­taa toi­sis­taan nel­jä kä­si­tet­tä.

• Merk­ki on pe­rus­yk­sik­kö, jois­ta kie­len il­mauk­set ra­ken­ne­taan. Merk­ke­jä voi­vat ol­la esi­mer­kik­si isot ja pie­net kir­jai­met. Oh­jel­moin­ti­kiel­ten syn­tak­si­mää­rit­te­lys­sä mer­kit aja­tel­laan abstrak­tim­min si­ten, et­tä merk­kien roo­lis­sa ovat avain­sa­nat ku­ten if ja while, vä­li­mer­kit ja ope­raat­to­rit ku­ten ; ja ==, oh­jel­moi­jan tai kie­len suun­nit­te­li­jan an­ta­mat ni­met ku­ten n ja string, sel­lai­se­naan il­moi­te­tut ar­vot (ns. li­te­raa­li­va­kiot) ku­ten 3.14159 ja "torstai" ja niin edel­leen. Kaik­kien käy­tös­sä ole­vien merk­kien jouk­koa kut­su­taan aak­kos­tok­si.
• Merk­ki­jo­no on ää­rel­li­nen mää­rä merk­ke­jä pe­räk­käin. Myös nol­la merk­kiä sal­li­taan. Merk­ki­jo­noa, jos­sa on nol­la merk­kiä mer­ki­tään sym­bo­lil­la ε ja kut­su­taan tyh­jäk­si merk­ki­jo­nok­si. Jo­kai­nen merk­ki on merk­ki­jo­no, jon­ka pi­tuus on yk­si. Merk­ke­jä ja merk­ki­jo­no­ja voi har­joi­tel­la te­ke­mäl­lä teh­tä­vän Merk­ki­jo­not.
• Kie­li on jouk­ko merk­ki­jo­no­ja. Kie­len mää­ri­tel­mä ma­te­ma­tii­kas­sa on to­del­la­kin näin yk­sin­ker­tai­nen. Kie­li ei ole esi­mer­kik­si merk­ki­jo­no­jen ja nii­den mer­ki­tys­ten muo­dos­ta­ma jär­jes­tel­mä, vaan pel­käs­tään ne merk­ki­jo­not. Kie­li ei ole myös­kään sään­nös­tö jo­ka mää­rää, mit­kä merk­ki­jo­not ovat mu­ka­na ja mit­kä ovat ul­ko­na, vaan pel­käs­tään ne mu­ka­na ole­vat merk­ki­jo­not. Jan­ku­tan tä­tä, kos­ka ai­kai­sem­min mo­ni opis­ke­li­ja oli ym­mär­tä­nyt kie­len kä­sit­teen vää­rin, jou­tu­nut sen vuok­si ha­ko­teil­le muis­sa­kin kä­sit­teis­sä ja me­net­tä­nyt ten­tis­sä pal­jon pis­tei­tä. Si­nul­la on nyt hy­vä mah­dol­li­suus ol­la tois­ta­mat­ta sa­maa vir­het­tä.
• Kie­li­op­pi on sään­nös­tö jo­ka mää­rää, mit­kä merk­ki­jo­not kuu­lu­vat kie­leen ja mit­kä ei­vät kuu­lu. BNF on kei­no esit­tää kie­li­op­pe­ja.

Va­lit­se jo­kai­sel­le va­sem­man reu­nan olen­nol­le, on­ko se merk­ki (va­sen ruu­tu), on­ko se merk­ki­jo­no (kes­kim­mäi­nen ruu­tu) ja on­ko se kie­li (oi­kea ruu­tu) olet­taen, et­tä aak­kos­to­na on kir­jai­met.

k	only_no_yes_on ok_text En­sim­mäi­nen koh­ta oi­kein! hide_expr 2=hide_expr 0 tai
{k}	only_no_yes_on ok_text Toi­nen koh­ta oi­kein! hide_expr 1=hide_expr 0 tai
koira	only_no_yes_on ok_text Kol­mas koh­ta oi­kein! hide_expr 1=hide_expr 0 tai
{koira}	only_no_yes_on ok_text Nel­jäs koh­ta oi­kein! hide_expr 1=hide_expr 0 tai
koira, kissa, heppa	only_no_yes_on ok_text Vii­des koh­ta oi­kein! hide_expr 0=hide_expr 0 tai
{koira, kissa, heppa}	only_no_yes_on ok_text Kuu­des koh­ta oi­kein! hide_expr 1=hide_expr 0 tai
ε	only_no_yes_on ok_text Seit­se­mäs koh­ta oi­kein! hide_expr 1=hide_expr 0 tai
{ε}	only_no_yes_on ok_text Kah­dek­sas koh­ta oi­kein! hide_expr 1=hide_expr 0 tai

Al­la on en­sim­mäi­nen esi­merk­kim­me BNF-mää­ri­tel­mäs­tä eli BNF:llä il­mais­tus­ta kie­li­opis­ta. Se mää­rit­te­lee täs­mää­vien sul­ku­jo­no­jen kie­len.

S	::=	A | SA
A	::=	ε | (S)

Mää­ri­tel­mä an­taa mää­rit­te­le­män­sä kie­len ni­mek­si S. Sen aak­kos­tos­sa on kak­si merk­kiä: ”(” ja ”)”. Mää­ri­tel­mä käyt­tää apu­kä­sit­tee­nä tois­ta kiel­tä, jo­ta se kut­suu ni­mel­lä A. Kie­leen A kuu­lu­vat tyh­jä merk­ki­jo­no se­kä kaik­ki ne merk­ki­jo­not, jois­sa on alus­sa ”(”, sit­ten täs­mää­vä sul­ku­jo­no ja lo­puk­si ”)”. Muu­ta A:han ei kuu­lu. Kie­leen S kuu­lu­vat täs­mäl­leen ne merk­ki­jo­not, jot­ka saa­daan liit­tä­mäl­lä yh­den tai useam­pia A:han kuu­lu­via merk­ki­jo­no­ja pe­räk­käin.

Mää­ri­tel­mä sa­noo, et­tä S saa­daan kor­va­ta A:lla, S saa­daan kor­va­ta SA:lla, A saa­daan kor­va­ta tyh­jäl­lä merk­ki­jo­nol­la ja A saa­daan kor­va­ta (S):llä. Mää­ri­tel­mäs­tä voi­daan tuot­taa merk­ki­jo­no aloit­ta­mal­la S:stä ja kor­vaa­mal­la ny­kyi­ses­tä merk­ki­jo­nos­ta mi­kä ta­han­sa iso kir­jain kun­nes jäl­jel­lä ei enää ole iso­ja kir­jai­mia. Esi­mer­kik­si ()(()) voi­daan tuot­taa seu­raa­vas­ti:

• Aloi­te­taan sym­bo­lil­la S.
• Sään­nön S ::= SA no­jal­la S kor­va­taan SA:lla.
• Sään­nön A ::= (S) no­jal­la A kor­va­taan (S):llä, jol­loin saa­daan S(S).
• Sään­nön S ::= A no­jal­la en­sim­mäi­nen S kor­va­taan A:lla, jol­loin saa­daan A(S).
• Sään­nön A ::= (S) no­jal­la A kor­va­taan (S):llä, jol­loin saa­daan (S)(S).
• Sään­nön S ::= A no­jal­la en­sim­mäi­nen S kor­va­taan A:lla, jol­loin saa­daan (A)(S).
• Sään­nön A ::= ε no­jal­la A kor­va­taan tyh­jäl­lä merk­ki­jo­nol­la, jol­loin saa­daan ()(S).
• Sään­nön S ::= A no­jal­la S kor­va­taan A:lla, jol­loin saa­daan ()(A).
• Sään­nön A ::= (S) no­jal­la A kor­va­taan (S):llä, jol­loin saa­daan ()((S)).
• Sään­nön S ::= A no­jal­la S kor­va­taan A:lla, jol­loin saa­daan ()((A)).
• Sään­nön A ::= ε no­jal­la A kor­va­taan tyh­jäl­lä merk­ki­jo­nol­la, jol­loin saa­daan ()(()).

Yl­lä ole­va voi­daan esit­tää tii­viim­min näin: S → SA → S(S) → A(S) → (S)(S) → (A)(S) → ()(S) → ()(A) → ()((S)) → ()((A)) → ()(()). Jos jäl­jel­lä on ai­na­kin kak­si isoa kir­jain­ta, ei ole vä­liä, kum­pi niis­tä kor­va­taan en­sik­si. Esi­mer­kik­si osuu­des­sa SA → S(S) → A(S) kor­vat­tiin en­sin lo­pus­ta A ja sit­ten alus­ta S, mut­ta sa­maan ol­tai­siin pää­dyt­ty kor­vaa­mal­la en­sin alus­ta S ja sit­ten lo­pus­ta A, eli näin: SA → AA → A(S). Merk­ki­jo­non tuot­ta­mi­nen voi­daan esit­tää myös ku­va­na, ku­ten yl­lä teh­tiin. Täl­lai­sen ku­van esit­tä­mä puu­mai­nen ra­ken­ne tun­ne­taan ni­mel­lä jä­sen­nys­puu. Jä­sen­nys­puu ei ota kan­taa sii­hen, mi­kä iso kir­jain kor­va­taan en­sin.

Täs­sä voit ko­keil­la kuu­luu­ko merk­ki­jo­no täs­mää­vien sul­ku­jen kie­leen ja jos kuu­luu, mi­ten se muo­dos­tuu sään­tö­jen mu­kaan. Ko­kei­le merk­ki­jo­not (), (, )(, "" (tar­koit­taa tyh­jää merk­ki­jo­noa), ((())), ()()(), (()(), (()()), (())() se­kä it­se va­lit­se­mia­si merk­ki­jo­no­ja. Kat­so kie­leen kuu­lu­vien merk­ki­jo­no­jen jä­sen­nys­puut ja var­mis­ta, et­tä ym­mär­rät, mi­ten ku­kin kie­leen kuu­lu­va merk­ki­jo­no on tuo­tet­tu.
CFG_set S ::= A | SA A ::= "" | (S) ; CFG_tree tai

Seu­raa­va kie­li­op­pi muis­tut­taa pal­jon si­tä, mi­ten mo­nien oh­jel­moin­ti­kiel­ten lau­sek­keet on mää­ri­tel­ty. Sii­nä on kui­ten­kin jip­po tai pa­ri, jot­ta kaik­ki koh­dat ei­vät oli­si rat­kais­ta­vis­sa yleis­tie­dol­la vaan oli­si tar­peen hie­man miet­tiä, mi­tä se to­del­la mää­rit­te­lee.

Lauseke	::=	Tulo | Lauseke + Tulo | Lauseke − Tulo
Tulo	::=	Tekijä | Tulo · Tekijä | Tulo / Tekijä
Tekijä	::=	Atomi | + Atomi | − Tekijä
Atomi	::=	Luku | Muuttuja | ( Lauseke )

”Luku” on epä­tyh­jä jo­no nu­me­roi­ta ja ”Muuttuja” on kir­jain. Klik­kaa ruu­dut sen mu­kaan mi­hin kie­liin ri­vin alun merk­ki­jo­no kuu­luu. Ri­vin en­sim­mäi­nen ruu­tu vas­taa ato­mia, toi­nen te­ki­jää, kol­mas tu­loa ja nel­jäs lau­se­ket­ta.

6	ok_text Teit oi­keat va­lin­nat! only_no_yes_on hide_expr 0 = hide_expr 4 tai
(	ok_text Juu­ri niin! only_no_yes_on hide_expr 0 = hide_expr 0 tai
−x	ok_text Teit oi­keat va­lin­nat! only_no_yes_on hide_expr 0 = hide_expr 3 tai
+x	ok_text Juu­ri niin! only_no_yes_on hide_expr 0 = hide_expr 3 tai
−−x	ok_text Teit oi­keat va­lin­nat! only_no_yes_on hide_expr 0 = hide_expr 3 tai
+−x	ok_text Juu­ri niin! only_no_yes_on hide_expr 0 = hide_expr 0 tai
2·x·y	ok_text Teit oi­keat va­lin­nat! only_no_yes_on hide_expr 0 = hide_expr 2 tai
−2·+x·y	ok_text Juu­ri niin! only_no_yes_on hide_expr 0 = hide_expr 2 tai
3x	ok_text Teit oi­keat va­lin­nat! only_no_yes_on hide_expr 0 = hide_expr 0 tai
x−x	ok_text Juu­ri niin! only_no_yes_on hide_expr 0 = hide_expr 1 tai
+1++1	ok_text Teit oi­keat va­lin­nat! only_no_yes_on hide_expr 0 = hide_expr 1 tai
(3·x+1)	ok_text Juu­ri niin! only_no_yes_on hide_expr 0 = hide_expr 4 tai

Math­Checkin BNF-teh­tä­vis­sä kie­len ni­me­nä on ai­na iso kir­jain ja isot kir­jai­met tul­ki­taan ai­na kiel­ten ni­mik­si. Sik­si isot kir­jai­met ei­vät kuu­lu aak­kos­toon, eli nii­tä ei voi esiin­tyä lo­pul­li­sis­sa merk­ki­jo­nois­sa. Jos va­li­taan L = Lauseke, T = Tulo, E = Tekijä, A = Atomi, U = Luku ja M = Muuttuja, kor­va­taan · ja − hel­pom­min kir­joi­tet­ta­vil­la * ja - se­kä lais­ko­tel­laan Luvun ja Muuttujan koh­dal­la, niin äs­kei­nen kie­li­op­pi voi­daan esit­tää Math­Checkil­le näin:

L ::= T | L+T | L-T
T ::= E | T*E | T/E
E ::= A | +A | -E
A ::= U | M | (L)
U ::= 0 | 1 | 2
M ::= x | y | z

Sa­ma kie­li saa­daan toi­sel­la­kin kie­li­opil­la, jo­ka eroaa L:n ja T:n mää­ri­tel­mien osal­ta. Et löy­dä merk­ki­jo­noa, jo­ka kuu­luu toi­sen mut­ta ei toi­sen mää­ri­tel­män kie­leen, kos­ka ne tuot­ta­vat sa­man kie­len. Toi­saal­ta mel­kein jo­kai­sel­le merk­ki­jo­nol­le, jo­ka kuu­luu sii­hen kie­leen, tu­lee eri­lai­nen jä­sen­nys­puu eri mää­ri­tel­mis­tä. Ko­kei­le an­ne­tul­la merk­ki­jo­nol­la ja muu­ta­mil­la muil­la, ja ver­taa jä­sen­nys­puu­ta kie­li­op­piin.
L ::= T | L+T | L-T   ja   T ::= E | T*E | T/E
L ::= T | T+L | T-L   ja   T ::= E | E*T | E/T
E ::= A | +A | -E A ::= U | M | (L) U ::= 0 | 1 | 2 M ::= x | y | z ; CFG_tree 1+2-x*y/z tai

Tä­män esi­mer­kin kie­li­opeis­ta ylem­pi on si­kä­li pa­rem­pi, et­tä se vas­taa ma­te­ma­tii­kas­sa ja oh­jel­moin­ti­kie­lis­sä ta­val­li­ses­ti nou­da­tet­ta­vaa las­ku­jär­jes­tys­tä, mut­ta alem­pi ei vas­taa. Sik­si yleen­sä käy­te­tään ylem­pää. Täs­tä huo­li­mat­ta alem­pi­kin kie­li­op­pi tuot­taa sa­man kie­len, sil­lä se tuot­taa sa­mat merk­ki­jo­not, ei­kä ma­te­ma­tii­kas­sa kie­len kä­sit­tees­sä mil­lään muul­la ole vä­liä kuin mit­kä merk­ki­jo­not ovat mu­ka­na.

Sa­ma kie­li saa­daan myös mää­rit­te­le­mäl­lä L ja T seu­raa­vas­ti.

L ::= T | L+L | L-L
T ::= E | T*T | T/T

Täs­sä kie­li­opis­sa merk­ki­jo­nol­le 1+x-y (ja hy­vin mo­nel­le muul­le­kin) saa­daan kak­si eri jä­sen­nys­puu­ta, ku­ten ku­vis­ta nä­kyy. Kie­li­op­pia sa­no­taan mo­ni­se­lit­tei­sek­si (ambiguous), jos se tuot­taa ai­na­kin yh­del­le merk­ki­jo­nol­le kak­si eri jä­sen­nys­puu­ta. Jos ha­lu­taan, et­tä jä­sen­nys­puut vas­taa­vat merk­ki­jo­noil­le tar­koi­tet­tua mer­ki­tys­tä, niin mo­ni­se­lit­tei­syyt­tä pi­tää vält­tää. Mo­ni­se­lit­tei­syy­den vält­tä­mi­nen on kui­ten­kin toi­si­naan liian vai­keaa, jo­ten oh­jel­moin­ti­kie­lel­le tms. voi­daan jou­tua käyt­tä­mään mo­ni­se­lit­teis­tä kie­li­op­pia.

Al­la on mää­ri­tel­ty leik­ki­kie­len while-sil­muk­ka. Sii­hen si­säl­tyy eh­to ja lau­se. Eh­to muo­dos­tuu muut­tu­jas­ta, ver­tai­lu­ope­raat­to­ris­ta ja nu­me­ros­ta. Esi­mer­kin pi­tä­mi­sek­si ly­hye­nä eri­lai­sia muut­tu­jia jne. on tar­jol­la vain muu­ta­ma, ja lau­se voi ol­la vain kah­ta eri­lais­ta muo­toa ole­va si­joi­tus­lau­se. Vä­li­lyön­te­jä on pak­ko ol­la täs­mäl­leen ku­ten nii­tä on BNF-mää­ri­tel­mäs­sä. Kir­joi­ta kel­vol­li­nen sil­muk­ka. Jot­ta vas­tauk­ses­sa voi­si ol­la vä­li­lyön­te­jä, on se lai­tet­ta­va lai­naus­merk­kei­hin, mut­ta vai­va­si sääs­tä­mi­sek­si ne on an­net­tu val­mii­na.

S	::= while E do L
E	::= MVN
L	::= M := M | M := M-N
M	::= x | y
N	::= 0 | 1 | 2
V	::= = | >

CFG_set S ::= "while E do L" E ::= MVN L ::= "M := M" | "M := M-N" M ::= x | y N ::= 0 | 1 | 2 V ::= = | > ; CFG_CR_on CFG_tree "" tai

Tä­mä kie­li­op­pi syö­tet­tiin Math­Checkil­le näin:

S ::= "while E do L"
E ::= MVN
L ::= "M := M" | "M := M-N"
M ::= x | y
N ::= 0 | 1 | 2
V ::= = | >

Täs­sä vai­hees­sa on tar­peen ker­toa, mi­ten sym­bo­lin ::= oi­keal­la puo­lel­la ole­va vaih­to­eh­to kir­joi­te­taan Math­Checkil­le. Jos sii­nä ei ole vä­li­lyön­te­jä ei­kä se ala mer­kil­lä " ei­kä ', niin sen voi kir­joit­taa sel­lai­se­naan. Jos sii­nä ei ole merk­ke­jä ", niin sen voi kir­joit­taa merk­kien " vä­lis­sä. Jos sii­nä ei ole merk­ke­jä ', niin sen voi kir­joit­taa merk­kien ' vä­lis­sä. Mer­keil­lä " ja/tai ' ra­jat­tu­ja osuuk­sia voi ol­la pe­räk­käin, jol­loin Math­Check yh­dis­tää ne en­nen käyt­töä. Tä­mä pä­tee vaik­ka nii­den vä­lis­sä oli­si vä­li­lyön­te­jä tai ri­vin­siir­to­ja.

Kum­mal­le­kin al­la ole­vis­ta kie­li­opeis­ta an­na epä­tyh­jä merk­ki­jo­no, jo­ka kuu­luu sen mää­rit­te­le­mään kie­leen.
ok_text On­nis­tuit! CFG_set X ::= "" | NX N ::= 0 | 1 | 2 ; CFG_short 1 CFG_in
end_of_answer /*Jois­sa­kin olo­suh­teis­sa | saat­taa jou­tua osak­si merk­ki­jo­noa sen si­jaan et­tä se toi­mi­si vaih­to­eh­to­jen erot­ti­me­na.*/ CFG_set X ::= ""|NX N ::= 0|1|2 ; CFG_short 1 CFG_in
tai

Ri­vi X ::= ""|NX tul­ki­taan si­ten, et­tä …"" esit­tää tyh­jän merk­ki­jo­non, | il­moit­taa et­tä yk­si vaih­to­eh­to lop­puu ja seu­raa­va al­kaa, ja NX tar­koit­taa kie­leen N kuu­lu­vaa merk­ki­jo­noa jat­ket­tu­na kie­leen X kuu­lu­val­la merk­ki­jo­nol­la. Pys­ty­vii­va ei ole osa en­sim­mäis­tä vaih­to­eh­toa, kos­ka lai­naus­merk­ki lo­pet­taa en­sim­mäi­sen vaih­to­eh­don juu­ri en­nen si­tä.

Mää­rit­te­le if-lau­se, jos­sa on pa­kol­li­nen then-osa ja va­paa­eh­toi­nen else-osa. Sa­nat if, then ja else pi­tää erot­taa muus­ta täs­mäl­leen yh­del­lä vä­li­lyön­nil­lä, pait­si ai­van alus­sa ja ai­van lo­pus­sa. Osa vas­tauk­ses­ta on an­net­tu val­mii­na. On vai­keaa (ken­ties mah­do­ton­ta) löy­tää täl­le kie­li­op­pi, jo­ka ei ole mo­ni­se­lit­tei­nen, mut­ta voit to­ki yrit­tää. (Sen si­jaan saat­taa ol­la mah­dol­lis­ta löy­tää täl­le kie­li­op­pi, jos­ta Math­Check ei huo­maa, et­tä se on mo­ni­se­lit­tei­nen. Kie­li­opin mo­ni­se­lit­tei­syy­den tut­ki­mi­nen on las­ken­nal­li­ses­ti niin vai­keaa, et­tä mi­kään oh­jel­ma ei voi ai­na sel­vi­tä sii­tä.)
Kiel­lä mo­ni­se­lit­tei­syys
ok_text On­nis­tuit! CFG_set I ::= "if E then L" | "if E then L else L" E ::= M>N L ::= M:=N | I M ::= x N ::= 0 | 1 ; CFG_set2 I ::=
E ::= M>N L ::= M:=N | I M ::= x N ::= 0 | 1 ; CFG_compare
tai

Toi­vot­ta­vas­ti sait Math­Checkil­tä esi­mer­kin merk­ki­jo­nos­ta, jol­la on kak­si jä­sen­nys­puu­ta. Tä­mä il­miö tun­ne­taan ni­mel­lä ”dangling else”. Se rat­kais­taan yleen­sä il­mai­se­mal­la sa­nal­li­ses­ti, et­tä ku­kin else-haa­ra kuu­luu sii­hen lä­hin­nä edel­tä­vään if-lau­see­seen, jol­la ei jo ole else-haa­raa.

Sai­sim­me vä­li­lyön­tien käy­tön jous­ta­vam­mak­si mää­rit­te­le­mäl­lä apu­kie­len B ::= " " | " B". Oh­jel­moin­ti­kiel­ten mää­rit­te­lys­sä ei kui­ten­kaan yleen­sä teh­dä niin, vaan jae­taan mää­ri­tel­mä kah­teen ta­soon. Niin sa­no­tul­la lek­si­kaa­li­sel­la ta­sol­la mää­ri­tel­lään kie­len ne ra­ken­ne­osat, joi­den si­säl­lä ei voi ol­la vä­li­lyön­te­jä lain­kaan, ku­ten avain­sa­nat (esim. while) ja lu­ku­va­kiot (esim. 40100). Sa­mal­la ta­sol­la mää­ri­tel­lään niin sa­not­tu val­koi­nen ti­la, jo­ka tyy­pil­li­ses­ti voi si­säl­tää ai­na­kin vä­li­lyön­te­jä, ri­vin­siir­to­ja ja kom­ment­te­ja. Niin sa­no­tul­la var­si­nai­sen syn­tak­sin ta­sol­la avain­sa­no­ja, lu­ku­va­kioi­ta jne. käy­te­tään ikään kuin ne oli­si­vat mää­ri­tel­män merk­ke­jä. Mää­ri­tel­mäs­sä nii­tä lai­te­taan pe­räk­käin ot­ta­mat­ta kan­taa val­koi­sen ti­lan käyt­töön.

Suun­nit­te­le kie­li­op­pi muut­tu­jan x po­ly­no­meil­le. Ma­te­ma­tii­kas­sa esi­mer­kik­si −2x³ + 5 + x − 3x² on po­ly­no­mi. Po­ly­no­mi koos­tuu yh­des­tä tai useam­mas­ta ter­mis­tä, jot­ka on yh­dis­tet­ty toi­siin­sa ope­raat­to­ril­la + tai -. Li­säk­si ko­ko po­ly­no­min edes­sä voi ol­la -. Po­tens­si­las­ku esi­te­tään ope­raat­to­ril­la ^. Mo­ni­mut­kai­sim­mil­laan ter­mis­sä on lu­ku, x, ^ ja luon­nol­li­nen lu­ku, mut­ta alus­sa ole­va lu­ku voi puut­tua ja lop­pu­osuus al­kaen ^-mer­kis­tä voi puut­tua. Li­säk­si ter­mi voi ol­la pelk­kä lu­ku. Luon­nol­li­sia lu­ku­ja ovat (vain) 0, 1 ja 2, ja mui­ta lu­ku­ja ovat (vain) e ja pi. Jä­tä vä­li­lyön­nit ko­ko­naan pois.
ok_text Sait kai­ken täs­mää­mään! Hie­noa!
CFG_set P ::= T | -T | P+T | P-T T ::= Lx^N | Lx | x^N | x | L L ::= N | e | pi N ::= 0 | 1 | 2 ; CFG_set2 P ::= ; CFG_compare
tai

Merk­ki­jo­no on pa­lindro­mi jos ja vain jos se on sa­ma etu- ja ta­ka­pe­rin luet­tu­na. Tun­net­tu­ja esi­merk­ke­jä suo­men­kie­len pa­lindro­meis­ta ovat saippuakauppias ja innostunutsonni. Nyt aak­kos­to­na on {a, b, c}. Mää­rit­te­le pa­lindro­mit.
Kiel­lä mo­ni­se­lit­tei­syys
ok_text !NiiN! CFG_set P ::= "" | a | b | c | aPa | bPb | cPc ; CFG_set2 P ::= ; CFG_compare
tai

Edel­lä ol­lut täs­mää­vien sul­ku­jo­no­jen kie­li­op­pi on mo­ni­se­lit­tei­nen. Ku­ten ku­vat näyt­tä­vät, tyh­jä merk­ki­jo­no voi­daan tuot­taa sii­tä kah­del­la eri ta­val­la. Mää­rit­te­le sa­ma kie­li il­man mo­ni­se­lit­tei­syyt­tä. On ole­mas­sa ly­hyt oi­kea vas­taus, mut­ta si­tä ei eh­kä ole ihan help­po löy­tää.
ok_text Jesss! CFG_set S ::= A | SA A ::= "" | (S) ; CFG_ambiguous_on CFG_set2 S ::= ; CFG_compare
tai

Va­lit­se to­det väit­tä­mät. only_no_yes_on ok_text Oi­kein va­lit­sit! hide_expr 3 = hide_expr 0

	Sa­ma merk­ki voi kuu­lua kah­des­ti sa­maan merk­ki­jo­noon.
	Sa­ma merk­ki­jo­no voi kuu­lua kah­des­ti sa­maan merk­kiin.
	Sa­ma kie­li­op­pi voi tuot­taa kak­si eri kiel­tä.
	Sa­ma kie­li voi­daan tuot­taa kah­del­la eri kie­li­opil­la.
	Sa­ma kie­li­op­pi voi tuot­taa kak­si eri merk­ki­jo­noa.

tai

Va­lit­se oi­kea vaih­to­eh­to. only_no_yes_on ok_text Nyt tärp­pä­si! prop_logic hide_expr

	Kie­li on kaik­kien merk­ki­jo­no­jen jouk­ko.
	Kie­li on merk­ki­jo­no­jen jouk­ko.
	Kie­li on jouk­ko merk­ki­jo­no­ja.
	Kie­li on kie­li­opin tuot­ta­ma jouk­ko merk­ki­jo­no­ja.

tai

Jäl­jel­lä oli­si vaik­ka kuin­ka hie­no­ja BNF-teh­tä­viä, mut­ta eh­kä toi­sen ker­ran!