LR1 (1131548), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

end;

‚ ­ «¨§ â®à å ⨯ LR(0) ¯à¨ ¯®áâ஥­¨¨ closure ­¥ ãç¨âë¢ îâáï â¥à¬¨­ «ë ¨§ FIRST(va).

…᫨ I - ¬­®¦¥á⢮ á¨âã 権, ¤®¯ãá⨬ëå ¤«ï ­¥ª®â®à®£® ªâ¨¢­®£® ¯à¥ä¨ªá z, â® goto(I,X) - ¬­®¦¥á⢮ á¨âã 権, ¤®¯ãá⨬ëå ¤«ï ªâ¨¢­®£® ¯à¥ä¨ªá zX.

function goto(I,X);/*I - ¬­®¦¥á⢮ á¨âã 権;

X - ᨬ¢®« £à ¬¬ ⨪¨*/

begin �ãáâì [A->u.Xv,a] ¯à¨­ ¤«¥¦¨â I;

� áᬮâਬ J - ¬­®¦¥á⢮ á¨âã 権 [A-uX.v,a];

return closure(J)

end;

� ¡®â «£®à¨â¬ ¯®áâ஥­¨ï ¬­®¦¥á⢠LR(1)-á¨âã 権 ­ 稭 ¥âáï á ⮣®, çâ® ¡¥à¥âáï C - ¬­®¦¥á⢮ á¨âã 権 {closure({[S'->.S,$]})}. ‡ ⥬ ¨§ ¨¬¥î饣®áï ¬­®¦¥áâ¢ á ¯®¬®éìî ®¯¥à 樨 goto() áâà®ïâáï ­®¢ë¥ ¬­®¦¥á⢠á¨âã 権. �®-áãé¥áâ¢ã, goto(I,X) - ¯¥à¥å®¤ ª®­¥ç­®£® ¢â®¬ â ¨§ á®áâ®ï­¨ï I ¯® ᨬ¢®«ã X.

procedure items(G'); begin C:={closure({[S'->.S,$]})};

repeat ¤«ï ª ¦¤®£® ¬­®¦¥á⢠á¨âã 権 I ¨§ C

¨ ª ¦¤®£® ᨬ¢®« £à ¬¬ ⨪¨ X

â ª®£®, çâ® goto(I,X) ­¥ ¯ãáâ®

¨ ­¥ ¯à¨­ ¤«¥¦¨â C

do ¤®¡ ¢¨âì goto(I,X) ª C

until ª C ­¥«ì§ï ¡®«ìè¥ ¤®¡ ¢¨âì ¬­®¦¥á⢠á¨âã 権 end;

�ਬ¥à 3.8. � áᬮâਬ ¯®¯®«­¥­­ãî £à ¬¬ ⨪㠯ਬ¥à 3.5.

E'-> E

1) E -> E + T

2) E -> T

3) T -> T * F

4) T -> F

5) F -> id

Œ­®¦¥á⢮ á¨âã 権 ¨ ¯¥à¥å®¤®¢ ¤«ï í⮩ £à ¬¬ ⨪¨ ¯à¨¢¥¤¥­ë ­ à¨á. 3.19.

‚ ª ¦¤ë© ¬®¬¥­â ­ «¨§ ¢ ¬ £ §¨­¥ ­ 室¨âáï ªâ¨¢­ë© ¯à¥ä¨ªá, ª®â®àë© á®®â¢¥âáâ¢ã¥â ¯®á«¥¤®¢ ⥫쭮á⨠¯¥à¥å®¤®¢ ¨§ ­ ç «ì­®£® á®áâ®ï­¨ï (I₀) ¢ ⥪ã饥. ‘¢¥à⪠- íâ® § ¬¥­ áãää¨ªá ¯à¥ä¨ªá ¨ ¯¥à¥å®¤ ¢ ­®¢®¥ á®áâ®ï­¨¥, â.¥. ª ª ¡ë ¢®§¢à â ¯® ç á⨠¯ãâ¨, ᮮ⢥âáâ¢ãî饩 ®á­®¢¥, ¨ § ¬¥­ í⮩ ç á⨠¯¥à¥å®¤®¬, ᮮ⢥âáâ¢ãî騬 «¥¢®© ç áâ¨.

� áᬮâਬ ⥯¥àì, ª ª ¯® ¬­®¦¥áâ¢ã LR(1)-á¨âã 権 áâà®ïâáï ä㭪樨 ¤¥©áâ¢¨ï ¨ ¯¥à¥å®¤®¢ LR(1)- ­ «¨§ â®à . ”㭪樨 ¤¥©áâ¢¨ï ¨ ¯¥à¥å®¤®¢ ¯à¥¤áâ ¢«ïîâáï â ¡«¨æ¥©.

ÚÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ E ÚÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ + ÚÄÄÄÄÄÄÄÄÄÄÄÄÄ¿

³ I₀ ÃÄÄÄ>³ I₁ ÃÄÄÄ>³ I₄ ³

³ E'-> .E, $ ³ ³ E'-> E., $ ³ ³ E -> E+.T,$ ³

³ E -> .E+T,$ ³ ³ E -> E.+T,$ ³ ³ E -> E+.T,+ ³

³ E -> .T, $ ³ ³ E -> E.+T,+ ³ ³ T -> .T*F,$ ³

³ T -> .T*F,$ ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ³ T -> .F, $ ³

³ T -> .F, $ ³ T ÚÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ T -> .T*F,+ ³

³ F -> .id, $ ÃÄÄÄ>³ I2 ³ ³ T -> .F, + ³

³ E -> .E+T,+ ³ ³ E -> T., $ ³ ³ F -> .id, $ ³

³ E -> .T, + ³ ³ T -> T.*F,$ ³ ³ F -> .id, + ³

³ T -> .T*F,+ ³ ³ E -> T., + ³ ³ T -> .T*F,* ³

³ T -> .F, + ³ ³ T -> T.*F,+ ³ ³ T -> .F, * ³

³ T -> .T*F,* ³ ³ T -> T.*F,* ³ ³ F -> .id, * ³

³ T -> .F, * ³ ÀÄÄÂÄÄÄÄÄÄÄÄÄÄÙ ÀÄÄÄÂÄÄÄÂÄÄÂÄÄÙ

³ F -> .id, * ³ ³ F³ ³ ³

³ F -> .id, + ÃÄÄÄÄÄÄÄÅÄÄÄ¿ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ³ ³

ÀÄÂÄÄÄÄÄÄÄÄÄÄÄÙ ³ F ³ ³ T ³ ³ id

³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ³ ³ ³ ÀÄÄÄÄÄÄ¿

ÚÄÙ ³ * ³ ³ ³ ³

³ v v v v ³

³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÚÄÄÄÄÄÄÄÄÄÄÄ¿ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³

³ ³ I₇ ³ ³ I₃ ³ ³ I₅ ³ ³

³ ³ T -> T*.F,$ ³ ³ T -> F.,$ ³ ³ E -> E+T.,$ ³ ³

³ ³ T -> T*.F,+ ³ ³ T -> F.,+ ³ ³ E -> E+T.,+ ³ ³

³ ³ T -> T*.F,* ³ ³ T -> F.,* ³ ³ T -> T.*F,$ ³ ³

³ ³ F -> .id, $ ³ ÀÄÄÄÄÄÄÄÄÄÄÄÙ * ³ T -> T.*F,+ ³ ³

³ ³ F -> .id, + ³<ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´ T -> T.*F,* ³ ³

³ ³ F -> .id,* ³ id ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ³

³ ÀÄÄÄÄÂÄÄÄÂÄÄÄÄÙ ÚÄÄÄÄÙ

³ ³ F ³ id ³

³ id ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³

ÀÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ ³

³ ³ ³ ³

v v v v

ÚÄÄÄÄÄÄ-ÄÄÄÄÄÄ¿ F ÚÄÄÄÄÄÄÄÄÄÄÄÄ¿

³ I₈ ³ ³ I₆ ³

³ T -> T*F.,$ ³ ³ F -> id.,+ ³

³ T -> T*F.,+ ³ ³ F -> id.,* ³

³ T -> T*F.,* ³ ³ F -> id.,$ ³

ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ

�¨á. 3.19

€«£®à¨â¬ 3.9. �®áâ஥­¨¥ ª ­®­¨ç¥áª¨å â ¡«¨æ LR ­ «¨§ â®à .

˜ £1. ‘âந¬ ­ ¡®à ¬­®¦¥á⢠LR(1)- á¨âã 権 C={I₀,I₁,...,I_n} ¤«ï G'.

˜ £ 2. ‘®áâ®ï­¨¥ i ­ «¨§ â®à áâநâáï ¨§ I_i. „¥©áâ¢¨ï ­ «¨§ â®à ¤«ï á®áâ®ï­¨ï i ®¯à¥¤¥«ïîâáï á«¥¤ãî騬 ®¡à §®¬:

) ¥á«¨ [A->u.av,b] ¯à¨­ ¤«¥¦¨â I_i ¨ goto(I_i,a)=I_j, â® ¯®« £ ¥¬ action[i,a]="shift j". ‡¤¥áì a - â¥à¬¨­ «;

¡) ¥á«¨ [A->u.,a] ¯à¨­ ¤«¥¦¨â I_i, A#S', â® ¯®« £ ¥¬ action[i,a]="reduce A->u";

¢) ¥á«¨ [S'->S.,$] ¯à¨­ ¤«¥¦¨â I_i, ¯®« £ ¥¬ action[i,$]="accept".

˜ £ 3. �¥à¥å®¤ë ¤«ï á®áâ®ï­¨ï i ®¯à¥¤¥«ïîâáï á«¥¤ãî騬 ®¡à §®¬: ¥á«¨ goto(I_i,A)=I_j, â® goto[i,A]=j (§¤¥áì A - ­¥â¥à¬¨­ «).

˜ £ 4. ‚ᥠ¢å®¤ë, ­¥ ®¯à¥¤¥«¥­­ë¥ è £ ¬¨ 2 ¨ 3, ¯®« £ ¥¬ à ¢­ë¬¨ "error".

˜ £ 5. � ç «ì­®¥ á®áâ®ï­¨¥ ­ «¨§ â®à áâநâáï ¨§ ¬­®¦¥á⢠, ᮤ¥à¦ 饣® á¨âã æ¨î [S'->.S,$]. …᫨ ¯à¨ ¯à¨¬¥­¥­¨¨ íâ¨å ¯à ¢¨« ¢®§­¨ª ¥â ª®­ä«¨ªâ, â.¥. ¢ ®¤­®¬ ¨ ⮬ ¦¥ ¬­®¦¥á⢥ ¬®¦¥â ¡ëâì ¡®«¥¥ ®¤­®£® ¢ ਠ­â ¤¥©á⢨© («¨¡® ᤢ¨£/ᢥà⪠, «¨¡® ᢥà⪠/ᢥà⪠), £®¢®àïâ, çâ® £à ¬¬ ⨪ ­¥ ï¥âáï LR(1), ¨ «£®à¨â¬ § ¢¥àè ¥âáï ­¥ãᯥ譮.

’ ¡«¨æ , ¯®«ãç îé ïáï ¨§ ä㭪権 ­ «¨§ â®à action ¨ goto ¢ १ã«ìâ â¥ à ¡®âë €«£®à¨â¬ 3.10, ­ §ë¢ ¥âáï ª ­®­¨ç¥áª®© â ¡«¨æ¥© LR(1)- ­ «¨§ â®à . LR- ­ «¨§ â®à, à ¡®â î騩 ¯® í⮩ â ¡«¨æ¥, ­ §ë¢ ¥âáï ª ­®­¨ç¥áª¨¬ LR- ­ «¨§ â®à®¬. …᫨ äã­ªæ¨ï ­ «¨§ â®à action ­¥ ᮤ¥à¦¨â ­¥®¤­®§­ ç­® ®¯à¥¤¥«¥­­ëå ¢å®¤®¢, â® £à ¬¬ ⨪ ­ §ë¢ ¥âáï LR(1)-£à ¬¬ ⨪®©.

3.3.4. Š®­ä«¨ªâë à §¡®à ⨯ ᤢ¨£-ᢥàâª

…᫨ £à ¬¬ ⨪ ­¥ ï¥âáï LR(1), â® ­ «¨§ â®à ⨯ ᤢ¨£-ᢥà⪠¤«ï ­¥¥ ¬®¦¥â ¤®á⨣­ãâì ª®­ä¨£ãà 樨, ¢ ª®â®à®© ®­, §­ ï ᮤ¥à¦¨¬®¥ ¬ £ §¨­ ¨ á«¥¤ãî騩 ¢å®¤­®© ᨬ¢®«, ­¥ ¬®¦¥â à¥è¨âì, ¤¥« âì «¨ ᤢ¨£ ¨«¨ ᢥàâªã (ª®­ä«¨ªâ ᤢ¨£/ᢥà⪠), ¨«¨ ­¥ ¬®¦¥â à¥è¨âì, ª ªãî ¨§ ­¥áª®«ìª¨å ᢥà⮪ ¯à¨¬¥­¨âì (ª®­ä«¨ªâ ᢥà⪠/ᢥà⪠). ‚ ç áâ­®áâ¨, ­¥®¤­®§­ ç­ ï £à ¬¬ ⨪ ­¥ ¬®¦¥â ¡ëâì LR.

�ਬ¥à 3.9. � áᬮâਬ ¢­®¢ì á«¥¤ãîéãî £à ¬¬ ⨪㠮¯¥à â®à if-then-else:

St -> if Ex then St

| if Ex then St else St

| ...

…᫨ ­ «¨§ â®à ⨯ ᤢ¨£-ᢥà⪠­ 室¨âáï ¢ ª®­ä¨£ãà 樨

Œ £ §¨­ ‚室

... if Ex then St else ... $

â® ­¥«ì§ï ®¯à¥¤¥«¨âì, ï¥âáï «¨ if Ex then St ®á­®¢®©, ¢­¥ § ¢¨á¨¬®á⨠®â ⮣®, çâ® «¥¦¨â ¢ ¬ £ §¨­¥ ­¨¦¥. �â® ª®­ä«¨ªâ ᤢ¨£/ᢥà⪠. ‚ § ¢¨á¨¬®á⨠®â ⮣®, çâ® á«¥¤ã¥â ­ ¢å®¤¥ § else, ¯à ¢¨«ì­®© ¬®¦¥â ¡ëâì ᢥà⪠¯® St -> if Ex then St ¨«¨ ᤢ¨£ else, § ⥬ à §¡®à ¤à㣮£® St ¨ § ¢¥à襭¨¥ «ìâ¥à­ ⨢ë if Ex then St else St. ’ ª¨¬ ®¡à §®¬ ­¥«ì§ï ᪠§ âì, ­ã¦­® «¨ ¢ í⮬ á«ãç ¥ ¤¥« âì ᤢ¨£ ¨«¨ ᢥàâªã, â ª çâ® £à ¬¬ ⨪ ­¥ LR(1).

�â £à ¬¬ ⨪ ¬®¦¥â ¡ëâì ¯à¥®¡à §®¢ ­ ª LR(1)-¢¨¤ã á«¥¤ãî騬 ®¡à §®¬:

St -> CondSt | UnCondSt

CondSt -> IfThenSt | IfThenElseSt

FullSt -> IfThenElseSt | UnCondSt

IfThenElseSt -> if Ex then FullSt else St

IfThenSt ->if Ex then St

3.3.5. ‚®ááâ ­®¢«¥­¨¥ ¯®á«¥ ᨭ⠪á¨ç¥áª¨å ®è¨¡®ª

Ž¤­¨¬ ¨§ ¯à®á⥩è¨å ¬¥â®¤®¢ ï¥âáï á«¥¤ãî騩. �ਠᨭ⠪á¨ç¥áª®© ®è¨¡ª¥ ¯à®á¬ âਢ ¥¬ ¬ £ §¨­ ®â ¢¥àåã誨, ¯®ª ­¥ ­ ©¤¥¬ á®áâ®ï­¨¥ s á ¯¥à¥å®¤®¬ ­ ¢ë¤¥«¥­­ë© ­¥â¥à¬¨­ « A. ‡ ⥬ ᪠­¨àãîâáï ¢å®¤­ë¥ ᨬ¢®«ë, ¯®ª ­¥ ¡ã¤¥â ­ ©¤¥­ â ª®©, ª®â®àë© ¤®¯ãá⨬ ¯®á«¥ A. ‚ í⮬ á«ãç ¥ ­ ¢¥àåãèªã ¬ £ §¨­ ¯®¬¥é ¥âáï á®áâ®ï­¨¥ goto[s,A] ¨ à §¡®à ¯à®¤®«¦ ¥âáï. „«ï ­¥â¥à¬¨­ « A ¬®¦¥â ¨¬¥âìáï ­¥áª®«ìª® â ª¨å ¢ ਠ­â®¢. Ž¡ëç­® A - íâ® ­¥â¥à¬¨­ «, ¯à¥¤áâ ¢«ïî騩 ®¤­ã ¨§ ®á­®¢­ëå ª®­áâàãªæ¨© ï§ëª , ­ ¯à¨¬¥à ®¯¥à â®à. ’®£¤ s - íâ®, ­ ¯à¨¬¥à, â®çª á § ¯ï⮩ ¨«¨ end.

�ਠ¡®«¥¥ ¤¥â «ì­®© ¯à®à ¡®âª¥ ॠªæ¨¨ ­ ®è¨¡ª¨ ¬®¦­® ¢ ª ¦¤®© ¯ãá⮩ ª«¥âª¥ ­ «¨§ â®à ¯®áâ ¢¨âì ®¡à 饭¨¥ ª ᢮¥© ¯®¤¯à®£à ¬¬¥. ’ ª ï ¯®¤¯à®£à ¬¬ ¬®¦¥â ¢áâ ¢«ïâì ¨«¨ 㤠«ïâì ¢å®¤­ë¥ ᨬ¢®«ë ¨«¨ ᨬ¢®«ë ¬ £ §¨­ , ¬¥­ïâì ¯®à冷ª ¢å®¤­ëå ᨬ¢®«®¢.

Характеристики

Список файлов ответов (шпаргалок)