Voici un court exemple d'analyse lexicale et syntaxique en assembleur (x86, 32 bits).
Le programme analyse une expression algébrique et en donne le résultat. Par exemple : 3 + (5 - 2) renverra 6.
Vous pouvez télécharger l'exemple entier ici : ga.asm
Pour le compiler et l'exécuter :
nasm -f elf32 ga.asm
ld -melf_i386 -s -o ga ga.o
echo "3 + (4 - 2)" | ./ga
Quelques fonctions indispensable
Pour construire les analyseurs, il faut au préalable quelques fonctions. Les plus évidentes sont celles pour la lecture des données.
J'ai choisis ici de lire directement sur l'entrée standard. La fonction consume_char permet d'avancer d'un caractère, get_char de récupérer le caractère actuel. Il faut obligatoirement appeler consume_char une première fois avant de pouvoir utilier get_char.
section .text
; Retourne le caractère actuel
;
; Output :
; eax : le caractère actuel
get_char:
mov eax, [char]
ret
; Avance d'un caractère dans la lecture de l'entrée standard
;
; Output :
; eax : le caractère lu
consume_char:
; syscall
; eax : sysread
; ebx : stdin
; ecx : buffer
; edx : buffer size
mov eax, 3
mov ebx, 0
mov ecx, char
mov edx, 1
int 0x80
; si aucun caractère n'a été lu, il y a eut une erreur
; bien que l'erreur puisse etre de différentes,
; on supposera ici que l'on est arrivé à la fin du fichier
cmp eax, 1
jne consume_char_error
mov eax, [char]
; juste au cas ou...
and eax, 0x000000FF
mov [char], eax
ret
consume_char_error:
mov eax, -1
mov [char], eax
ret
section .data
char dd 0
Une fonction très simple pour afficher un caractère à l'écran.
section .text
; Affiche sur stdout le caractère contenu dans eax
;
; Input :
; eax : le caractère à afficher
print_char:
push eax
; syscall
; eax : syswrite
; ebx : stdout
; ecx : buffer (ici le haut de la pile)
; edx : buffer size
mov eax, 4
mov ebx, 1
mov ecx, esp
mov edx, 1
int 0x80
pop eax
ret
Il nous faut une fonction pour afficher le résultat. Pour faire simple, on va l'afficher en binaire.
section .text
; Affiche sur l'entrée standard un nombre binaire
;
; Input :
; eax : le nombre à afficher
print_bin:
; Pour savoir quand on a afficher tous les caractère
push dword '2'
; La méthode est assez simple :
; On fait des rotation à droite jusqu'à ce
; ce que eax = 0
; Si le carry est à 1 après une rotation,
; il faut afficher 1, sinon 0.
; On récupère les bits dans l'ordre inverse
; de l'affichage, donc on utilise une pile pour inverser
print_bin_bcl:
mov ebx, '0'
shr eax, 1
adc ebx, 0
push ebx
test eax, eax
jnz print_bin_bcl
pop eax
print_bin_bcl_2:
call print_char
pop eax
cmp eax, '2'
jne print_bin_bcl_2
ret
Et une dernière très simple pour quitter le programme :
section .text
; quitte le programme
exit:
; syscall
; eax = sysexit
mov eax,1
int 0x80
Fonctions d'erreur
Dans cet exemple très simple, on a 2 types d'erreur qui peuvent survenir :
- Lecture d'un caractère inattendu, provoqué par l'analyseur lexical
- Mauvaise suite de token ou fin de fichier inattendu, provoqué par l'analyseur syntaxique
Lorsqu'une de ces erreurs surviennent, on affiche un message et on quitte. A part en cas de fin de fichier inattendu, on pourrait simplement ignorer tous les caractères/token jusqu'à ce qu'on trouve quelque chose qui nous convienne.
section .text
; Function à appeller en cas d'erreur
; pendant l'analyse syntaxique
;
; Input :
; eax : le token invalide
error_unexpected_token:
push eax
mov edx, error_unexpected_token_len
mov ecx, error_unexpected_token_msg
mov ebx, 2
mov eax, 4
int 0x80
pop eax
add eax, '0'
call print_char
mov eax, 0xa
call print_char
jmp exit
; Function à appeller en cas d'erreur
; pendant l'analyse lexicale
;
; Input :
; eax : le caractère invalide
error_unexpected_char:
push eax
mov edx, error_unexpected_char_len
mov ecx, error_unexpected_char_msg
mov ebx, 2
mov eax, 4
int 0x80
pop eax
call print_char
mov eax, 0xa
call print_char
jmp exit
section .data
error_unexpected_char_msg db 'Unexpected char : '
error_unexpected_char_len equ $ - error_unexpected_char_msg
error_unexpected_token_msg db 'Unexpected token : '
error_unexpected_token_len equ $ - error_unexpected_token_msg
Analyse lexicale
L'analyseur lexicale sera utilisé par l'analyseur syntaxique par le biais de 2 fonctions :
- get_token : retourne le token actuel
- consume_token : se déplace au token suivant et le retourne
Tout comme pour la lecture des caractère, consume_token doit être appelé une première fois avant de pouvoir utiliser get_token.
Le fonctionnement de l'analyseur lexical est très simple. On lit un caractère. Les espaces, les tabulations et les retours à la ligne sont ignorés. Si il correspond à un token, on retourne ce token. Si il correspond au début d'un token plus long (un entier dans notre cas), on essaie de le découvrir en entier. Sinon, il y a une erreur.
ebx est utilisé pour retourner des données associés au token. Dans cet exemple, il sera seulement utilisé pour les entiers pour renseigner leur valeur (une fois convertie).
section .text
; Retourne le token actuel
;
; Output :
; eax : le token actuel
; ebx : données associés au token, si besoin
get_token:
mov eax, [token]
mov ebx, [token_data]
ret
; Se déplace au token suivant et le retourne
;
; Output :
; eax : le token actuel
; ebx : données associés au token, si besoin
consume_token_consume_char:
call consume_char
consume_token:
call get_char
; ignore les espace, etc
cmp eax, ' '
je consume_token_consume_char
cmp eax, 0x08 ; tab
je consume_token_consume_char
cmp eax, 0x0a ; \n
je consume_token_consume_char
cmp eax, 0x0d ; \r
je consume_token_consume_char
; on teste si le caractère correspond à un token "simple"
consume_token_case_0:
cmp eax, '-'
jne consume_token_case_1
mov eax, TOKEN_MINUS
jmp consume_token_case_end
consume_token_case_1:
cmp eax, '+'
jne consume_token_case_2
mov eax, TOKEN_PLUS
jmp consume_token_case_end
consume_token_case_2:
cmp eax, '('
jne consume_token_case_3
mov eax, TOKEN_OPEN
jmp consume_token_case_end
consume_token_case_3:
cmp eax, ')'
jne consume_token_case_4
mov eax, TOKEN_CLOSE
jmp consume_token_case_end
; si on a le début d'un entier
; on le découvre et on le convertie
consume_token_case_4:
cmp eax, '0'
jb consume_token_case_5
cmp eax, '9'
ja consume_token_case_5
mov ebx, 0
; on boucle tant qu'il y a des chiffres
consume_token_discover_int:
cmp eax, '0'
jb consume_token_discover_int_end
cmp eax, '9'
ja consume_token_discover_int_end
; valeur de l'entier
sub eax, '0'
; ebx = ebx * 10 + eax
shl ebx, 1
mov ecx, ebx
shl ebx, 2
add ebx, ecx
add ebx, eax
push ebx
call consume_char
pop ebx
jmp consume_token_discover_int
consume_token_discover_int_end:
mov eax, TOKEN_NUM
jmp consume_token_exit_without_consume_char
consume_token_case_5:
cmp eax, -1
jne consume_token_case_default
mov eax, TOKEN_EOF
jmp consume_token_case_end
consume_token_case_default:
call error_unexpected_char
consume_token_case_end:
mov [token], eax
mov [token_data], ebx
call consume_char
ret
; sortie de la fonction pour les tokens à plusieurs caractère
consume_token_exit_without_consume_char:
mov [token], eax
mov [token_data], ebx
ret
section .data
token dd 0
token_data dd 0
Analyse syntaxique
L'analyse syntaxique est légèrement plus compliqué que l'analyse lexicale.
Voici les deux règles que nous avons, où S est l'axiome et num un nombre :
- S := T ( ( '+' | '-' ) T ) *
- T := '(' S ')' | num
On peut réécrire S de cette manière, où 1 est le mot vide :
- S := T S2
- S2 := '+' T S2 | '-' T S2 | 1
On a ici une grammaire non contextuel sur laquelle on va effectuer une analyse ascendante.
Le mot vide dans la règle S2 doit être compris de cette façon : si, dans S2, on lit en première un caractère qui ne nous intéresse pas (autre chose que '+' ou '-'), on retourne à la règle précédente.
Généralement un AST est construit lors de l'analyse syntaxique. Ici on va plus simplement calculer le résultat de l'expression arithmétique.
section .text
;
; S2 := '+' T S2 | '- T S2 | 1
;
; Input :
; eax : la valeur de l'opérande de gauche
;
; Output :
; eax : le résultat de l'opéeation
;
rule_S2:
; on sauvegarde l'opérande de gauche en attendant de faire l'opération
push eax
call get_token
rule_S2_case_1:
cmp eax, TOKEN_PLUS
jne rule_S2_case_2
call consume_token
call rule_T
; addition
pop ebx
add eax, ebx
; "récursion"
call rule_S2
ret
rule_S2_case_2:
cmp eax, TOKEN_MINUS
jne rule_S2_default
call consume_token
call rule_T
; soustraction
pop ebx
sub ebx, eax
mov eax, ebx
; "récursion"
call rule_S2
ret
rule_S2_default:
pop eax
ret
;
; T -> (S) | 0..9
;
; Output :
; eax : valeur de l'opération ou du nombre
;
rule_T:
call get_token
rule_T_case_1:
cmp eax, TOKEN_OPEN
jne rule_T_case_2
call consume_token
call rule_S
push eax
; on vérifie qu'on a bien la paranthèse fermente
call get_token
cmp eax, TOKEN_CLOSE
jne error_unexpected_token
call consume_token
pop eax
ret
rule_T_case_2:
cmp eax, TOKEN_NUM
jne rule_T_case_default
push ebx
call consume_token
pop eax
ret
rule_T_case_default:
jmp error_unexpected_token
Fonction principale
; obligatoire
call consume_char
call consume_token
; appelle de l'axiome
call rule_S
push eax
; Si il reste quelque chose => erreur de syntaxe
call get_token
cmp eax, TOKEN_EOF
jne error_unexpected_token
pop eax
; on affiche le résultat
call print_bin
mov eax, 0xa
call print_char
call exit