LL(1) grammatika - Szó felismerés Macro Assemblerben

LL1 grammatika

Ez a program egy egyelőre fix szabálykészlet alapján egy LL(1) grammatika elemzést végez. Egy bekért inputot próbál megfeleltetni a szabályoknak. Majd kiírja, hogy sikerült-e vagy sem. Közben az elemző vermének tartalmát is lépésenként megjeleníti, valamint az épp beolvasott karaktert, hogy követni lehessen a folyamatot.

A program egy egyetemi előadáshoz készült. Az előadáshoz, és a program elkészítéséhez szükséges információkat Dévai Gergely ( ELTE-IK ) prezentációjából szereztem.



Az előző néhány assembly programhoz hasonlóan, ezt is masm 6.11 fejlesztőkörnyezettel fordítottam. Lényeges információ a sikeres fordítás szempontjából :) Megint csak nem kommentelném a forráskódot hosszan, hiszen a kódban levő kommentek is elég részletesek. Ha valaki véletlenül hibát vélne felfedezni a programban, kérem szóljon, hogy abból is tanuljak. Az alábbi program ugyanis nálam több gépen is működött teszteléskor, ám mikor egyetemen az előadáson be szerettem volna mutatni, azon a gépen már nem futott le, amelyiken ki kellett volna vetítenem. Ma (2010.04.10.) rájöttem, hogy kihagytam a dsinit eljárás végén a ret kulcsszót. Valószínű ezért nem működött a program megfelelően.

A prezentációk és a program letölthető a következő linken is:
Letöltés


  1.     .model small
  2.     .stack
  3.     .data
  4.         cr = 13     ;carrige return (kocsi vissza)
  5.         lf = 10     ;line feed (uj sor)
  6.         tab = 9     ;tabulator
  7.         bckspc = 8  ;backspace a torleshez
  8.                
  9.         startszimb = 'S'  ;szabalyok start szimboluma
  10.  
  11.         start0 db 0    ;szabaly blokk kezdete
  12.         b1 db 'S',1    ;szabaly bal oldala. 1-es az elvalaszto karakter
  13.         j1 db 'aS',0   ;jobb oldal. A szabaly vege a 0
  14.         b2 db 'S',1
  15.         j2 db 'bAc',0
  16.         b3 db 'A',1
  17.         j3 db 'bAc',0
  18.         b4 db 'A',1
  19.         j4 db 'd',0
  20.         maxindex = $   ;A szabaly blokk vege. dollar az aktualis cim
  21.                
  22.         prompt db 'Adj meg egy mondatot: ',0   ;kiirando uzenetek
  23.         msgSzab db 'Szabalylista: ',0
  24.         msgVeremTart db 'Verem: ',0
  25.         msgAktKar db 'Aktualis karakter: ',0
  26.         msgJo db 'Felismertem ezt a szot!',0
  27.         msgNemJo db 'Ez bizony nem felel meg a szabalyoknak',0
  28.                
  29.         dcrlf db cr,lf,0   ;uj sor
  30.         sep db ': ',0      ;az 1-es karaktert erre csereli
  31.         bool db 0          ;boolean valtozo
  32.         tmpchr db 0        ;ideiglenes valtozok
  33.         tmpNT db 0
  34.                
  35.         verem db 255 dup(' '),0   ;a verem. max 255 karakteres
  36.         vmut db 0                 ;verem mutato
  37.         input db 255 dup(0)       ;az inputnak előre lefoglalt 255 karakter
  38.     .code
  39.  
  40. dsinit proc          ;adatszegmens inicializalasa
  41.     push ax
  42.  
  43.     mov ax, @data    ;adatszegmens kezdocime ax-be
  44.     mov ds, ax       ;ezt betoltjuk az adatszegmens regiszterbe
  45.  
  46.     pop ax
  47.     ret
  48. dsinit endp
  49.        
  50. clrscr proc        ;DOS kepernyo torlese
  51.     push ax    ;ax mentese
  52.     mov ax, 3  ;3-as bekerul ah-ba. Utasitas kepernyo torlesere
  53.     int 10h    ;hexa 10-es megszakitas. Kepernyo driver hivasara
  54.     pop ax
  55.     ret
  56. clrscr endp
  57.        
  58. gotoNextStr proc          ;ugrik az adatszegmensben a kov stringre
  59.     .while 1
  60.        mov dl, [di]
  61.        or dl, dl
  62.            .break .if zero?        
  63.        inc di
  64.     .endw
  65.     inc di
  66.     ret
  67. gotoNextStr endp
  68.                
  69. writem macro string       ;atadott karakter kiirasa kepernyore
  70.     push bx
  71.    
  72.     lea bx, string
  73.     call write_string
  74.    
  75.     pop bx
  76. endm
  77.        
  78. write_string proc         ;dl-ben levo kezdocimtol string kiirasa
  79.     push dx
  80.     push bx
  81.  
  82.     .while 1
  83.       mov dl, [bx]
  84.       or dl, dl
  85.       .break .if zero?   ;flag regiszter zero bitje ha 1, akkor kilep
  86.       .if dl == 1
  87.           writem sep
  88.           .else
  89.           call write_char
  90.       .endif
  91.       inc bx
  92.     .endw
  93.    
  94.     pop bx
  95.     pop dx
  96.     ret
  97. write_string endp
  98.  
  99. write_char proc ;dl-ben varja mit kell kiirni
  100.     push ax     ; ax stack -be mentese
  101.  
  102.     mov ah, 2h  ; Kiiras kodja
  103.     int 21h
  104.        
  105.     pop ax      ; ax-be a stackbol adat kivetele
  106.     ret
  107. write_char endp
  108.        
  109. writem_char macro chr    ;atadott karakter kiirasa kepernyore
  110.     push dx
  111.        
  112.     mov dl, chr
  113.     call write_char
  114.        
  115.     pop dx
  116. endm
  117.                                
  118. write_tab macro num     ;num darab tabulator kiirasa
  119.     local _end          ;lokalis cimke. Kell, mert a makro tobbszor fut
  120.     push dx             ;es minden alkalommal behelyettesiti a forrast
  121.     push cx
  122.        
  123.     mov dl, tab
  124.         mov cx, num
  125.     .if cx == 0         ;ha 0 volt a tabok szaba, akkor kilep
  126.        jmp _end
  127.     .endif
  128.     .repeat             ;ciklus amig cx nem nulla
  129.        call write_char
  130.     .untilcxz
  131.        
  132.   _end:
  133.     pop cx
  134.     pop dx     
  135. endm
  136.                
  137. szablista proc              ;szabalyok listajaak kiirasa
  138.     push di
  139.  
  140.     lea di, b1              ;az elso szabaly kezdocime di-be
  141.     .while (di < maxindex)  ;ciklus amig di kisebb az utolso szabaly vegenek cimenel
  142.        write_tab 1
  143.        writem [di]
  144.        call linebreak
  145.        call gotoNextStr
  146.     .endw
  147.  
  148.     pop di
  149.     ret
  150. szablista endp
  151.  
  152. linebreak proc        ;sortores
  153.     writem dcrlf
  154.     ret
  155. linebreak endp
  156.  
  157. kovszab macro NT, chr  ;kovszab
  158.     local vege         ;lokalis cimke
  159.     push dx
  160.     push ax
  161.  
  162.     mov tmpNT, NT      ;NT jelet el kell menteni,
  163.                        ;mert dl regiszter felul lesz irva
  164.        
  165.     lea di, b1         ;elso szabaly kezdocime
  166.     .repeat
  167.        mov dl, [di]    ;aktualis karakter a szabalyokbol
  168.        .if dl == tmpNT    ;ha a szabaly karaktere nem terminalis
  169.                
  170.            inc di
  171.            inc di
  172.            mov dl, [di]   ;ugras a szabaly job oldalara
  173.                    
  174.            .if dl == chr  ;ha a jobb oldal elso karaktere az amit keresunk
  175.                 _pop dl   ;kivesszuk a verembol
  176.                 call gotoNextStr  ;ugras a kovetkezo stringre
  177.                 dec di            ;vissza ugras az elozo string utolso karakterere
  178.                 dec di
  179.                 .while 1               ;ciklus
  180.                     mov dh, [di]
  181.                     .break .if dh == 1  ;amig nem elvalaszto karakter jon
  182.                                    
  183.                    _push dh            ;verembe betesszuk az uj szabaly karaktereit
  184.                    dec di              ;index  dekrementalasa
  185.                 .endw
  186.                                
  187.                 jmp vege               ;ha ide eljut, akkor megvan a szabaly
  188.            .endif
  189.        .endif  
  190.         call gotoNextStr      ;ugras a kovetkezo szabalyra
  191.     .until di > maxindex     ;amig nem erte el az utolso szabaly veget
  192.    
  193.     jmp eznemjo        ;ha nem talalta meg a szabalyt, akkor hiba
  194.  
  195.   vege:
  196.     mov NT, tmpNT      ;ertekek visszaallitasa
  197.        
  198.     pop ax
  199.     pop dx
  200. endm
  201.  
  202. _pop macro chr      ;verembol ertek chr beirasa. mutato novelese
  203.     push bx
  204.  
  205.     dec vmut
  206.     xor bx, bx
  207.     mov bl, vmut
  208.     mov chr, verem[bx]
  209.        
  210.     pop bx     
  211. endm
  212.  
  213. _push macro chr   ;vereme chr beirasa
  214.     push bx
  215.  
  216.     xor bx, bx
  217.     mov bl, vmut
  218.     mov verem[bx], chr
  219.     inc vmut
  220.        
  221.     pop bx     
  222. endm
  223.  
  224. _top macro chr    ;mutato allitasa nelkul utolso karakter a verembol chr-be
  225.     push bx
  226.  
  227.     xor bx, bx
  228.     mov bl, vmut
  229.     dec bl
  230.     mov chr, verem[bx]
  231.  
  232.     pop bx
  233. endm
  234.  
  235. write_verem proc       ;verem tartalmanak kiirasa
  236.     push dx
  237.  
  238.     _push 0
  239.     writem [verem+1] ;az elso karakter nula. Ezert a 2. tol kell kezdeni
  240.     _pop dl
  241.  
  242.     pop dx
  243.     ret
  244. write_verem endp
  245.  
  246. isTerm macro chr           ;ha chr terminalis, akkor bool = 1, egyebkent bool = 0
  247.     push di
  248.     push dx
  249.  
  250.     mov bool, 1
  251.     mov tmpchr, chr
  252.     lea di, b1
  253.     .repeat
  254.        mov dl, [di]       ;egyenloseg vizsgalat
  255.        sub dl, tmpchr
  256.        .if zero?          ;ha egyenlo volt a chr egy terminalis jellel,
  257.           mov bool, 0     ;azaz zero flag 1-es, akkor nem terminalis
  258.            .break
  259.        .endif
  260.        call gotoNextStr   ;ugras a kovetkezo szabalyra
  261.     .until di > maxindex  ;amig index kisebb az utolso szabaly vegenek cimenel
  262.  
  263.     pop dx
  264.     pop di
  265. endm
  266.  
  267. read_char proc                  ;egy karakter beolvasasa
  268.     push ax                             ;ax regiszter mentese
  269.        
  270.     mov ah, 1                   ;karakter bekeres kodja
  271.     int 21h                             ;hexa 21 -es megszakitas DOS-funkciok hivasahoz
  272.                                                 ;A karakter ekkor AL regiszterbe kerül
  273.        
  274.     mov dl, al                  ;A karakter-t a DL regiszterbe tesszuk
  275.  
  276.     pop ax                              ;ax visszatoltese
  277.     ret                                 ;visszateres subrutinbol
  278. read_char endp
  279.  
  280. readw proc
  281.     push dx                             ;regiszterek tartalmanak elmentese
  282.     push ax
  283.     push cx
  284.     push bx
  285.        
  286.     xor bx, bx
  287.   readw_r_start:                ;karakterek olvasasanak kezdete
  288.     call read_char              ;egy karakter beolvasasa. Eredmeny a dl regiszterbe kerul
  289.  
  290.     .if dl != cr
  291.        mov input[bx], dl
  292.        inc bx
  293.        .if dl != bckspc
  294.           jmp readw_r_start
  295.        .endif
  296.        writem_char ' '          ;egyebkent az elozo karakter torlese a kepernyon
  297.        writem_char bckspc       ;majd visszapozicionalas a torolt karakter helyere
  298.  
  299.        dec bx
  300.        mov input[bx], ' '
  301.        dec bx
  302.        mov input[bx], ' '
  303.        
  304.        jmp readw_r_start        ;ciklus vege. Ha eddig eljut, kezdi elolrol
  305.     .endif
  306.     mov input[bx], 0
  307.     call linebreak
  308.  
  309.     pop bx
  310.     pop cx                              ;regiszterek visszaallitasa a verembol
  311.     pop ax
  312.     pop dx
  313.        
  314.     ret                                 ;kilepes a subrutinbol
  315. readw endp
  316.  
  317. debug proc                  ;aktualisertekek kiirasa
  318.     writem msgVeremTart
  319.     call write_verem
  320.     writem_char ' '
  321.     write_tab 1
  322.        
  323.     writem msgAktKar
  324.     writem_char input[bx]
  325.        
  326.     call linebreak
  327.     ret
  328. debug endp
  329.  
  330. main proc                ;LL(1) szo felismerese
  331.     call dsinit
  332.     call clrscr          ;keperyno torlese
  333.                
  334.     writem prompt        ;szo bekerese
  335.     call readw    
  336.        
  337.     call linebreak
  338.     writem msgSzab      ;szabalyok listaja
  339.     call linebreak
  340.     call szablista
  341.     call linebreak
  342.                
  343.     _push 0
  344.     _push startszimb  ;start szimbolummal kezdunk a veremben
  345.  
  346.     xor bx, bx
  347.     .repeat       ;ciklus, amig nem ertunk a verem vegere
  348.         _top dl   ;verem teteje dl-be
  349.  
  350.         .if dl == 0   ;ha a verem ures
  351.            call debug    
  352.               .if input[bx] == 0   ;es ha az input vegere ertunk
  353.                  jmp ezjo ;akkor felismertuk a nyelvet
  354.               .else                                        
  355.                  jmp eznemjo ;egyebkent hiba
  356.               .endif
  357.         .endif
  358.                        
  359.         isTerm dl  ;ha terminalis jel volt dl, boolba 1 kerul. ha nem, boolba 0 kerul
  360.  
  361.         .if bool == 1           ;ha terminalis volt
  362.             .if dl == input[bx] ;ha egyezik a beolvasando karakterel
  363.                  call debug      
  364.                 _pop dl         ;kivesszuk a verembol
  365.                 inc bx          ;ugras a kov karakterre inputban
  366.             .else               ;egyebkent hiba. Nem ismerheto fel a szo
  367.                 call debug
  368.                 jmp eznemjo    
  369.             .endif
  370.         .else                    ;ha nem terminalis jel volt
  371.             call debug
  372.             kovszab dl, input[bx]  ;akkor keressuk a kovetkezo szabalyt
  373.                        
  374.         .endif
  375.     .until dl == 0 ;verem vege, ha dl-ben nulla volt
  376.        
  377.     jmp ezjo
  378.   eznemjo:
  379.     call linebreak
  380.     writem msgNemJo
  381.     jmp vege
  382.   ezjo:
  383.     call linebreak
  384.         writem msgJo
  385.   vege:  
  386.     .EXIT
  387. main endp      
  388.        
  389.                
  390. end main
Kategóriák: 
Megosztás/Mentés

Új hozzászólás