Teh­tä­vä:
Bac­kus–Naur Form

Täs­sä teh­tä­väs­sä tu­tus­tu­taan BNF:ään eli Bac­kus-Naur-for­miin. 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 con­text-free gram­mar) eli CFG.

John Bac­kus ja Pe­ter 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ä sansk­rii­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ä.

Kä­sit­tei­tä

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 abst­rak­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­tet­tä­vis­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ä kut­su­taan tyh­jäk­si merk­ki­jo­nok­si. Kun merk­ki­jo­not ra­ja­taan lai­naus­mer­keil­lä, se esi­te­tään "". Kun merk­ki­jo­not esi­te­tään sel­lai­si­naan, si­tä mer­ki­tään sym­bo­lil­la ε, kos­ka tyh­jä merk­ki­jo­no sel­lai­se­naan esi­tet­ty­nä ei näy, kos­ka se on ei mi­tään. 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.

Tie­dät­hän, et­tä eräs ta­pa esit­tää jouk­ko on lue­tel­la sen al­kiot aal­to­sul­keis­sa. Esi­mer­kik­si nel­jää pie­nem­pien luon­nol­lis­ten lu­ku­jen jouk­ko on {0, 1, 2, 3}.

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 /*Au­to, jos­sa on yk­si ih­mi­nen, ei ole ih­mi­nen vaan au­to. Kie­li, jos­sa on yk­si merk­ki­jo­no, ei ole merk­ki­jo­no vaan kie­li.*/ 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

Oh­jel­moin­ti­kiel­ten merk­ki­jo­no­va­kiois­sa ei voi­da esit­tää kaik­kia merk­ke­jä sel­lai­si­naan. Sik­si käy­te­tään epä­suo­ria kei­no­ja. C++-kie­les­sä merk­ki­jo­no esi­te­tään lai­naus­merk­kien " vä­lis­sä. Mo­net mer­kit voi­daan kir­joit­taa merk­ki­jo­noon sel­lai­si­naan. Sel­lai­set mer­kit esit­tä­vät it­seään. Lai­naus­merk­kiä ei voi käyt­tää esit­tä­mään it­seään, kos­ka sil­le on an­net­tu eri teh­tä­vä: se lo­pet­taa merk­ki­jo­non. Sik­si on otet­tu käyt­töön toi­nen kei­no: merk­ki­jo­noon si­säl­ty­vä lai­naus­merk­ki esi­te­tään \".

Merk­ki \ ei esi­tä it­seään il­mauk­ses­sa \", vaan ker­too, et­tä " ei lo­pe­ta­kaan merk­ki­jo­noa vaan tä­hän koh­taan tu­lee lai­naus­merk­ki. Merk­ki­jo­noon saa­daan \ kir­joit­ta­mal­la \\.

Kie­li, jo­ta ol­laan mää­rit­te­le­mäs­sä, on koh­de­kie­li. Kei­not, joil­la koh­de­kie­li mää­ri­tel­lään, ovat me­ta­kie­li. C++:n merk­ki­jo­no­jen ta­pauk­ses­sa "he\"i!" on me­ta­kie­len il­maus, jo­ka tuot­taa koh­de­kie­len merk­ki­jo­non he"i!.

Me­ta­kie­les­sä ja koh­de­kie­les­sä on ta­val­li­ses­ti pal­jon sa­mo­ja merk­ke­jä. Esi­mer­kik­si pie­net kir­jai­met kuu­lu­vat usein mo­lem­piin. Me­ta­kie­les­sä voi ol­la myös merk­ke­jä, joi­ta koh­de­kie­les­sä ei ole. Edel­lä ε oli täl­lai­nen. Koh­de­kie­les­sä voi ol­la merk­ke­jä, joi­ta me­ta­kie­les­sä ei ole. Esi­mer­kik­si näp­päi­mis­tös­sä­ni ei ole merk­kiä ε, mut­ta sil­ti sain sen esiin­ty­mään täl­lä vep­pi­si­vul­la.

Va­lit­se jo­kai­sel­le va­sem­man reu­nan olen­nol­le, tuot­taa­ko se koh­de­kie­len mer­kin (va­sen ruu­tu), tuot­taa­ko se koh­de­kie­len merk­ki­jo­non (seu­raa­va ruu­tu), on­ko se me­ta­kie­len merk­ki (seu­raa­va ruu­tu) ja on­ko se me­ta­kie­len merk­ki­jo­no (oi­kea ruu­tu) olet­taen, et­tä koh­de­kie­len 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 4=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 2=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
ε	only_no_yes_on ok_text Vii­des koh­ta oi­kein! hide_expr 3=hide_expr 0 tai
{ε}	only_no_yes_on ok_text Kuu­des koh­ta oi­kein! hide_expr 1=hide_expr 0 tai

Il­maus ”tuot­taa koh­de­kie­len merk­ki­jo­non” on kan­kea. Si­tä käy­te­tään kun ha­lu­taan ko­ros­taa koh­de­kie­len ja me­ta­kie­len eroa, mut­ta ei­pä juu­ri muul­loin. Ta­val­li­ses­ti sa­no­taan ”on merk­ki­jo­no”. Em­me­hän myös­kään sa­no ”42 tuot­taa pa­ril­li­sen lu­vun”, vaan ”42 on pa­ril­li­nen”. Sik­si äs­kei­nen oi­kea vas­taus ”ε tuot­taa koh­de­kie­len merk­ki­jo­non” tar­koit­taa sa­maa kuin ai­kai­sem­man koh­dan oi­kea vas­taus ”ε on merk­ki­jo­no”.

Jos käy­te­tään sa­naa ”merk­ki” tai ”merk­ki­jo­no” ker­to­mat­ta, tar­koi­te­taan­ko koh­de- vai me­ta­kie­len merk­kiä tai merk­ki­jo­noa, niin ta­val­li­ses­ti tar­koi­te­taan koh­de­kie­len.

Tar­kas­tel­laan kiel­tä {ankka, kana, ε, naakka}.
Kuin­ka mon­ta merk­ki­jo­noa sii­nä on? only_no_yes_on ok_text Oi­kein! arithmetic f_nodes 1 hide_expr 4 =
Kuin­ka mon­ta eri merk­kiä sen merk­ki­jo­nois­sa esiin­tyy? Vih­jeNiis­sä esiin­tyy merk­ke­jä a, k ja n. ε ei ole merk­ki. end_of_answer arithmetic f_nodes 1 hide_expr 3 =
Kuin­ka mon­ta merk­kiä sen merk­ki­jo­nois­sa on yh­teen­sä? Vih­jeMerk­ki­jo­nos­sa ank­ka on vii­si merk­kiä. Merk­ki­jo­nos­sa ε on nol­la merk­kiä. end_of_answer arithmetic f_nodes 1 hide_expr 15 =
tai

BNF-mää­ri­tel­mien tul­kin­ta

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ä. Kos­ka S ei kuu­lu aak­kos­toon, on (S) me­ta­kie­len mut­ta ei koh­de­kie­len merk­ki­jo­no. Mää­ri­tel­mäs­tä voi­daan tuot­taa koh­de­kie­len merk­ki­jo­no aloit­ta­mal­la me­ta­kie­len merk­ki­jo­nos­ta S ja kor­vaa­mal­la ny­kyi­ses­tä me­ta­kie­len 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ä, mi­kä 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.

Lau­se­ke	::=	Tu­lo | Lau­se­ke + Tu­lo | Lau­se­ke − Tu­lo
Tu­lo	::=	Te­ki­jä | Tu­lo · Te­ki­jä | Tu­lo / Te­ki­jä
Te­ki­jä	::=	Ato­mi | + Ato­mi | − Te­ki­jä
Ato­mi	::=	Lu­ku | Muut­tu­ja | ( Lau­se­ke )

”Lu­ku” on epä­tyh­jä jo­no nu­me­roi­ta ja ”Muut­tu­ja” 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. Jos et saa rat­kais­tua jo­tain ri­viä, niin lue pi­tem­mäl­le, rat­kai­se ri­vi siel­tä löy­ty­väl­lä työ­ka­lul­la, ja pa­laa ta­kai­sin tä­hän.

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ä koh­de­kie­len merk­ki­jo­nois­sa. Jos va­li­taan L = Lau­se­ke, T = Tu­lo, E = Te­ki­jä, A = Ato­mi, U = Lu­ku ja M = Muut­tu­ja, kor­va­taan · ja − hel­pom­min kir­joi­tet­ta­vil­la * ja - se­kä lais­ko­tel­laan Lu­vun ja Muut­tu­jan 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 | 3 | 6
M ::= x | y | z

Al­la voit tes­ta­ta merk­ki­jo­non kuu­lu­mi­sen mi­hin ta­han­sa äs­ken mää­ri­tel­lyis­tä kie­lis­tä. Kyl­lä-ta­pauk­sis­sa saat jä­sen­nys­puut. Rat­kai­se sen avul­la ne koh­dat, jot­ka edel­lä jäi­vät rat­kea­mat­ta. Muis­ta kir­joit­taa * ja - ei­kä · ja −. CFG_set L ::= T | L+T | L-T T ::= E | T*E | T/E E ::= A | +A | -E A ::= U | M | (L) U ::= 0 | 1 | 2 | 3 | 6 M ::= x | y | z ;
L T E A U M
CFG_CR_on CFG_tree " " tai

Tu­lee­ko merk­ki­jo­nois­ta 1+2+3, (1+2)+3 ja 1+(2+3) yk­si, kak­si vai kol­me eri­lais­ta jä­sen­nys­puu­ta kie­les­sä L? Mie­ti en­sin it­se ja sit­ten ko­kei­le yl­lä ole­val­la vas­taus­ruu­dul­la.

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 | 3 | 6 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 (am­bi­guous), jos ja vain jos se tuot­taa ai­na­kin yh­del­le merk­ki­jo­nol­le ai­na­kin 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.

To­den­ma­kui­sia esi­merk­ke­jä

En­nen kuin voim­me esit­tää oh­jel­moin­ti­kiel­ten kal­tai­sia esi­merk­ke­jä, on ker­rot­ta­va eräs asia. Ar­vaa kum­pi ohei­sis­ta ku­vis­ta on tä­hän men­nes­sä esi­te­tyn pe­rus­teel­la oi­kea jä­sen­nys­puu merk­ki­jo­nol­le

const int loppu = alku+42;

ohei­ses­sa kie­li­opis­sa?

D ::= "T M = L;"
T ::= K | "T K"
K ::= int | const
M ::= alku | loppu
L ::= V | M | L+V | L+M
V ::= 42

ok_text Oi­kein ar­va­sit! fail_text Vää­rin me­ni! prop_logic only_no_yes_on hide_expr TT <=> tai

Ar­vaa kum­pi on opet­ta­jan mie­les­tä sel­vem­pi. ok_text Tot­ta kai! fail_text Älä viit­si, olet­ko to­sis­sa­si? prop_logic only_no_yes_on hide_expr TT <=>
ylem­pi
alem­pi
tai

Mo­net oh­jel­moin­ti­kie­let rat­kai­se­vat tä­män on­gel­man ja­ka­mal­la syn­tak­sin kah­teen ta­soon: lek­si­kaa­li­set sään­nöt ja var­si­nai­nen syn­tak­si.

Lek­si­kaa­li­set sään­nöt mää­rää­vät mi­ten niin sa­no­tut teks­ti­al­kiot koo­taan yk­sit­täi­sis­tä mer­keis­tä. Tyy­pil­lis­ten oh­jel­moin­ti­kiel­ten teks­ti­al­kioi­ta ovat muun muas­sa va­kio­ar­vot ku­ten 123 ja "merk­ki­jo­no\n", ni­met ku­ten x, avain­sa­nat ku­ten while se­kä muut it­se­näi­sen mer­ki­tyk­sen omaa­vat merk­ki­yh­dis­tel­mät ku­ten <, =, <=, + ja ++.

Lek­si­kaa­li­set sään­nöt mää­rää­vät myös mi­kä on niin sa­not­tua val­kois­ta ti­laa, mis­sä si­tä saa ol­la, ja mis­sä si­tä pi­tää ol­la. Tyy­pil­li­ses­ti si­tä ovat ai­na­kin vä­li­lyön­nit, ri­vin­siir­rot ja kom­men­tit. Tyy­pil­li­ses­ti si­tä ei saa ol­la teks­ti­al­kioi­den si­säl­lä ja saa ol­la mi­ten pal­jon ta­han­sa teks­ti­al­kioi­den vä­lis­sä (ja ko­ko oh­jel­man alus­sa ja lo­pus­sa). Tyy­pil­li­ses­ti si­tä täy­tyy ol­la esi­mer­kik­si kir­jai­mis­ta koos­tu­vien teks­ti­al­kioi­den vä­lis­sä.

Ruk­si va­sem­paan reu­naan ne, jot­ka ovat lail­li­sia si­joi­tus­lau­sei­ta C++:ssa. Ruk­si toi­seen sa­rak­kee­seen ne, jot­ka ovat lail­li­sia muut­tu­jan mää­rit­te­ly­jä C++:ssa. ok_text Hy­vä, oi­kein! arithmetic only_no_yes_on hide_expr 4 = hide_expr 0

		intia = suurimaa;
		intia = suuri maa;
		int ia = suurimaa;
		int ia = suuri maa ;
		int ia=suurimaa ;
		int ia =            suurimaa ;

tai

Var­si­nai­nen syn­tak­si mää­rää mi­ten isom­mat ra­ken­teet koo­taan teks­ti­al­kiois­ta. Sii­nä käy­te­tään teks­ti­al­kioi­ta ikään kuin ne oli­si­vat mää­ri­tel­män merk­ke­jä. Sen esit­tä­mi­ses­sä käy­te­tään val­kois­ta ti­laa ih­mi­sel­le luon­te­val­la ta­val­la, ei­kä esi­tys­ta­pa ota kan­taa sii­hen, mi­ten si­tä kai­ken kaik­kiaan saa ja pi­tää käyt­tää. Esi­mer­kik­si muut­tu­jan mää­rit­te­lyn syn­tak­sik­si saa­te­taan an­taa seu­raa­va:

tyyppi nimi = alkuarvo;

Vaik­ka sii­nä on vä­li­lyön­nit =-mer­kin ym­pä­ril­lä, ne ei­vät ole C++:ssa vält­tä­mät­tö­mät. Vaik­ka sii­nä ei ole vä­li­lyön­tiä ;-mer­kin edes­sä, sel­lai­sen saa C++:ssa kir­joit­taa. Vaik­ka sii­nä kaik­ki on sa­mal­la ri­vil­lä, sen saa ja­kaa mo­nel­le ri­vil­le.

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.

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

Math­Checkin BNF-moo­diin ei ole ra­ken­net­tu eril­lis­tä lek­si­kaa­lis­ta ta­soa. Sik­si vä­li­lyön­nit ovat sil­le merk­ke­jä ku­ten muut­kin mer­kit, ja nii­tä on ol­ta­va täs­mäl­leen kul­loi­sen­kin BNF-mää­ri­tel­män mu­kai­ses­ti. Jä­sen­nys­pui­den saa­mi­sek­si hel­pom­min luet­ta­vak­si Math­Checkiin on kui­ten­kin ra­ken­net­tu kik­ka, jol­la mon­ta pe­räk­käis­tä merk­kiä voi lii­ma­ta yh­dek­si teks­ti­al­kiok­si.

Kir­joi­ta kel­vol­li­nen sil­muk­ka. Edel­lä mai­ni­tus­ta syys­tä 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ä, ja ne tu­le­vat nä­ky­viin jä­sen­nys­puus­sa. 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.
CFG_set S ::= "$while$ E $do$ L" E ::= MVN L ::= "M $:=$ N" | "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. Merk­ki­yh­dis­tel­mien while, do ja := ym­pä­ril­lä on $ osoit­ta­mas­sa, et­tä ku­kin niis­tä tu­lee tul­ki­ta yh­dek­si teks­ti­al­kiok­si.

S ::= "$while$ E $do$ L"
E ::= MVN
L ::= "M $:=$ N" | "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 ei ole vä­li­lyön­tiä. Osa vas­tauk­ses­ta on an­net­tu val­mii­na.
Kiel­lä mo­ni­se­lit­tei­syys Vih­je"if E then Y else L"
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

Ken­ties 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ä ”dang­ling 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ä lek­si­kaa­li­seen ta­soon ja var­si­nai­sen syn­tak­sin ta­soon, ku­ten edel­lä ker­rot­tiin.

Seu­raa­vak­si suun­nit­te­lem­me kie­li­opin 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 P koos­tuu yh­des­tä tai useam­mas­ta ter­mis­tä 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 N ovat (vain) 0, 1 ja 2, ja mui­ta lu­ku­ja ovat (vain) e ja pi. Luon­nol­li­set ja muut lu­vut muo­dos­ta­vat yh­des­sä kie­len L. Jä­tä vä­li­lyön­nit ko­ko­naan pois.

Si­nun ei ole pak­ko käyt­tää apu­kie­liä T, N ja L jos et ha­lua. Jos ha­luat, niin voit vas­taus­laa­ti­kon ala­puo­lel­ta va­li­ta, min­kä kie­len Math­Check tar­kas­taa. Sil­lä het­kel­lä tar­peet­to­mat mää­ri­tel­mät saa­vat ol­la laa­ti­kos­sa, kun­han ne ovat muo­dol­li­ses­ti kel­vol­li­sia. 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 ::= "pyyhi tämä vasta kun teet tähän muuta" ; P T L N CFG_compare
tai

Lo­puk­si

Merk­ki­jo­no on pa­lind­ro­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­lind­ro­meis­ta ovat saippuakauppias ja innostunutsonni. Nyt aak­kos­to­na on {a, b, c}. Mää­rit­te­le pa­lind­ro­mit.
Kiel­lä mo­ni­se­lit­tei­syys
ok_text !No niin oN! 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!