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


    .model small
    .stack
    .data
        cr = 13     ;carrige return (kocsi vissza)
        lf = 10     ;line feed (uj sor)
        tab = 9     ;tabulator
        bckspc = 8  ;backspace a torleshez
               
        startszimb = 'S'  ;szabalyok start szimboluma

        start0 db 0    ;szabaly blokk kezdete
        b1 db 'S',1    ;szabaly bal oldala. 1-es az elvalaszto karakter
        j1 db 'aS',0   ;jobb oldal. A szabaly vege a 0
        b2 db 'S',1
        j2 db 'bAc',0
        b3 db 'A',1
        j3 db 'bAc',0
        b4 db 'A',1
        j4 db 'd',0
        maxindex = $   ;A szabaly blokk vege. dollar az aktualis cim
               
        prompt db 'Adj meg egy mondatot: ',0   ;kiirando uzenetek
        msgSzab db 'Szabalylista: ',0
        msgVeremTart db 'Verem: ',0
        msgAktKar db 'Aktualis karakter: ',0
        msgJo db 'Felismertem ezt a szot!',0
        msgNemJo db 'Ez bizony nem felel meg a szabalyoknak',0
               
        dcrlf db cr,lf,0   ;uj sor
        sep db ': ',0      ;az 1-es karaktert erre csereli
        bool db 0          ;boolean valtozo
        tmpchr db 0        ;ideiglenes valtozok
        tmpNT db 0
               
        verem db 255 dup(' '),0   ;a verem. max 255 karakteres
        vmut db 0                 ;verem mutato
        input db 255 dup(0)       ;az inputnak előre lefoglalt 255 karakter
    .code

dsinit proc          ;adatszegmens inicializalasa
    push ax

    mov ax, @data    ;adatszegmens kezdocime ax-be
    mov ds, ax       ;ezt betoltjuk az adatszegmens regiszterbe

    pop ax
    ret
dsinit endp
       
clrscr proc        ;DOS kepernyo torlese
    push ax    ;ax mentese
    mov ax, 3  ;3-as bekerul ah-ba. Utasitas kepernyo torlesere
    int 10h    ;hexa 10-es megszakitas. Kepernyo driver hivasara
    pop ax
    ret
clrscr endp
       
gotoNextStr proc          ;ugrik az adatszegmensben a kov stringre
    .while 1
       mov dl, [di]
       or dl, dl
           .break .if zero?        
       inc di
    .endw
    inc di
    ret
gotoNextStr endp
               
writem macro string       ;atadott karakter kiirasa kepernyore
    push bx
   
    lea bx, string
    call write_string
   
    pop bx
endm
       
write_string proc         ;dl-ben levo kezdocimtol string kiirasa
    push dx
    push bx

    .while 1
      mov dl, [bx]
      or dl, dl
      .break .if zero?   ;flag regiszter zero bitje ha 1, akkor kilep
      .if dl == 1
          writem sep
          .else
          call write_char
      .endif
      inc bx
    .endw
   
    pop bx
    pop dx
    ret
write_string endp

write_char proc ;dl-ben varja mit kell kiirni
    push ax     ; ax stack -be mentese

    mov ah, 2h  ; Kiiras kodja
    int 21h
       
    pop ax      ; ax-be a stackbol adat kivetele
    ret
write_char endp
       
writem_char macro chr    ;atadott karakter kiirasa kepernyore
    push dx
       
    mov dl, chr
    call write_char
       
    pop dx
endm
                               
write_tab macro num     ;num darab tabulator kiirasa
    local _end          ;lokalis cimke. Kell, mert a makro tobbszor fut
    push dx             ;es minden alkalommal behelyettesiti a forrast
    push cx
       
    mov dl, tab
        mov cx, num
    .if cx == 0         ;ha 0 volt a tabok szaba, akkor kilep
       jmp _end
    .endif
    .repeat             ;ciklus amig cx nem nulla
       call write_char
    .untilcxz
       
  _end:
    pop cx
    pop dx     
endm
               
szablista proc              ;szabalyok listajaak kiirasa
    push di

    lea di, b1              ;az elso szabaly kezdocime di-be
    .while (di < maxindex)  ;ciklus amig di kisebb az utolso szabaly vegenek cimenel
       write_tab 1
       writem [di]
       call linebreak
       call gotoNextStr
    .endw

    pop di
    ret
szablista endp

linebreak proc        ;sortores
    writem dcrlf
    ret
linebreak endp

kovszab macro NT, chr  ;kovszab
    local vege         ;lokalis cimke
    push dx
    push ax

    mov tmpNT, NT      ;NT jelet el kell menteni,
                       ;mert dl regiszter felul lesz irva
       
    lea di, b1         ;elso szabaly kezdocime
    .repeat
       mov dl, [di]    ;aktualis karakter a szabalyokbol
       .if dl == tmpNT    ;ha a szabaly karaktere nem terminalis
               
           inc di
           inc di
           mov dl, [di]   ;ugras a szabaly job oldalara
                   
           .if dl == chr  ;ha a jobb oldal elso karaktere az amit keresunk
                _pop dl   ;kivesszuk a verembol
                call gotoNextStr  ;ugras a kovetkezo stringre
                dec di            ;vissza ugras az elozo string utolso karakterere
                dec di
                .while 1               ;ciklus
                    mov dh, [di]
                    .break .if dh == 1  ;amig nem elvalaszto karakter jon
                                   
                   _push dh            ;verembe betesszuk az uj szabaly karaktereit
                   dec di              ;index  dekrementalasa
                .endw
                               
                jmp vege               ;ha ide eljut, akkor megvan a szabaly
           .endif
       .endif  
        call gotoNextStr      ;ugras a kovetkezo szabalyra
    .until di > maxindex     ;amig nem erte el az utolso szabaly veget
   
    jmp eznemjo        ;ha nem talalta meg a szabalyt, akkor hiba

  vege:
    mov NT, tmpNT      ;ertekek visszaallitasa
       
    pop ax
    pop dx
endm

_pop macro chr      ;verembol ertek chr beirasa. mutato novelese
    push bx

    dec vmut
    xor bx, bx
    mov bl, vmut
    mov chr, verem[bx]
       
    pop bx     
endm

_push macro chr   ;vereme chr beirasa
    push bx

    xor bx, bx
    mov bl, vmut
    mov verem[bx], chr
    inc vmut
       
    pop bx     
endm

_top macro chr    ;mutato allitasa nelkul utolso karakter a verembol chr-be
    push bx

    xor bx, bx
    mov bl, vmut
    dec bl
    mov chr, verem[bx]

    pop bx
endm

write_verem proc       ;verem tartalmanak kiirasa
    push dx

    _push 0
    writem [verem+1] ;az elso karakter nula. Ezert a 2. tol kell kezdeni
    _pop dl

    pop dx
    ret
write_verem endp

isTerm macro chr           ;ha chr terminalis, akkor bool = 1, egyebkent bool = 0
    push di
    push dx

    mov bool, 1
    mov tmpchr, chr
    lea di, b1
    .repeat
       mov dl, [di]       ;egyenloseg vizsgalat
       sub dl, tmpchr
       .if zero?          ;ha egyenlo volt a chr egy terminalis jellel,
          mov bool, 0     ;azaz zero flag 1-es, akkor nem terminalis
           .break
       .endif
       call gotoNextStr   ;ugras a kovetkezo szabalyra
    .until di > maxindex  ;amig index kisebb az utolso szabaly vegenek cimenel

    pop dx
    pop di
endm

read_char proc                  ;egy karakter beolvasasa
    push ax                             ;ax regiszter mentese
       
    mov ah, 1                   ;karakter bekeres kodja
    int 21h                             ;hexa 21 -es megszakitas DOS-funkciok hivasahoz
                                                ;A karakter ekkor AL regiszterbe kerül
       
    mov dl, al                  ;A karakter-t a DL regiszterbe tesszuk

    pop ax                              ;ax visszatoltese
    ret                                 ;visszateres subrutinbol
read_char endp

readw proc
    push dx                             ;regiszterek tartalmanak elmentese
    push ax
    push cx
    push bx
       
    xor bx, bx
  readw_r_start:                ;karakterek olvasasanak kezdete
    call read_char              ;egy karakter beolvasasa. Eredmeny a dl regiszterbe kerul

    .if dl != cr
       mov input[bx], dl
       inc bx
       .if dl != bckspc
          jmp readw_r_start
       .endif
       writem_char ' '          ;egyebkent az elozo karakter torlese a kepernyon
       writem_char bckspc       ;majd visszapozicionalas a torolt karakter helyere

       dec bx
       mov input[bx], ' '
       dec bx
       mov input[bx], ' '
       
       jmp readw_r_start        ;ciklus vege. Ha eddig eljut, kezdi elolrol
    .endif
    mov input[bx], 0
    call linebreak

    pop bx
    pop cx                              ;regiszterek visszaallitasa a verembol
    pop ax
    pop dx
       
    ret                                 ;kilepes a subrutinbol
readw endp

debug proc                  ;aktualisertekek kiirasa
    writem msgVeremTart
    call write_verem
    writem_char ' '
    write_tab 1
       
    writem msgAktKar
    writem_char input[bx]
       
    call linebreak
    ret
debug endp

main proc                ;LL(1) szo felismerese
    call dsinit
    call clrscr          ;keperyno torlese
               
    writem prompt        ;szo bekerese
    call readw    
       
    call linebreak
    writem msgSzab      ;szabalyok listaja
    call linebreak
    call szablista
    call linebreak
               
    _push 0
    _push startszimb  ;start szimbolummal kezdunk a veremben

    xor bx, bx
    .repeat       ;ciklus, amig nem ertunk a verem vegere
        _top dl   ;verem teteje dl-be

        .if dl == 0   ;ha a verem ures
           call debug    
              .if input[bx] == 0   ;es ha az input vegere ertunk
                 jmp ezjo ;akkor felismertuk a nyelvet
              .else                                        
                 jmp eznemjo ;egyebkent hiba
              .endif
        .endif
                       
        isTerm dl  ;ha terminalis jel volt dl, boolba 1 kerul. ha nem, boolba 0 kerul

        .if bool == 1           ;ha terminalis volt
            .if dl == input[bx] ;ha egyezik a beolvasando karakterel
                 call debug      
                _pop dl         ;kivesszuk a verembol
                inc bx          ;ugras a kov karakterre inputban
            .else               ;egyebkent hiba. Nem ismerheto fel a szo
                call debug
                jmp eznemjo    
            .endif
        .else                    ;ha nem terminalis jel volt
            call debug
            kovszab dl, input[bx]  ;akkor keressuk a kovetkezo szabalyt
                       
        .endif
    .until dl == 0 ;verem vege, ha dl-ben nulla volt
       
    jmp ezjo
  eznemjo:
    call linebreak
    writem msgNemJo
    jmp vege
  ezjo:
    call linebreak
        writem msgJo
  vege:  
    .EXIT
main endp      
       
               
end main

Kategóriák: 
Megosztás/Mentés