Analizzatore lessicale Analizzatore lessicale
Legge la stringa in input e la trasforma in un flusso di token da sottoporre all’analizzatore sintattico.
Le frasi di un linguaggio sono stringhe di token (simboli atomici).
Richieste
Richieste per per l’analizzatorel’analizzatore lessicalelessicale::
1. Rimuovere spazi, tabulazioni, a capo, . . .
2. Raccogliere i digit in interi, in modo che nella
parsificazione i numeri siano trattati come elementi atomici: 3 + 25 – 2
<num, 3> <+, > < num, 25> <-, > < num, 2>
3. Riconoscere parole chiave e identificatori:
count = count + inc id = id + id
Per l’analisi sintattica non è importante conoscere i lessemi associati ad ogni identificatore, ma lo è per la traduzione.
Quando in input viene identificato un lessema, esso viene
memorizzato nella symbol table e il puntatore alla entry nella symbol table diventa un attributo del token id.
Le parole chiave di solito soddisfano le regole per la costruzione degli identificatori, quindi serve un meccanismo per decidere quando un lessema forma una parola chiave o un identificatore.
È più facile se le parole chiave sono riservate: un lessema è un id solo se non è una keyword.
input
lettura di un carattere
Analizzatore
lessicale Parsificatore
ritorno indietro
di un carattere token e attributi
L’analizzatore lessicale e il parsificatore formano una coppia produttore – consumatore: l’analizzatore produce i token e il parsificatore li consuma.
Come dimensionare il buffer?
Di solito il buffer contiene un token: l’interazione può essere implementata con una chiamata da parte del parsificatore della procedura di analisi lessicale, che ritorna i token su richiesta.
Anche per l’input di solito viene usato un buffer in cui viene letto un blocco di caratteri alla volta.
Analizzatore Analizzatore
lessicale lessicale
ritorno indietro di un carattere
lettura di un
carattere Restituzione di un
token al chiamante
tokenval tokenval
Variabile globale che contiene il valore dell’attributo
L’analizzatore restituisce la codifica del token, di solito un numero maggiore della codifica dei caratteri (256 . . .)
function lexan begin
while true do c := readcar
if c = ‘ ’ or ‘tab’ then do nothing
else if c = newline then lineno := lineno + 1
else if isdigit (c) then “costruisci il numero formato da c e dai digit successivi in tokenval”
return il token num
else if isalfa (c) then “identifica c e lettere e digit successivi come lessema”
“aggiorna la symbol table”
. . .
return il token id
else tokenval := NONE return c
end
function lexan begin
while true do c := readchar
if c = ‘ ‘ or ‘tab’ then do nothing
else if c = newline then lineno := lineno + 1 else if isdigit (c)
then tokenval := c c := readchar
while isdigit (c) do
tokenval := tokenval * 10 + c c := readchar
c := prechar return num . . .
Operazioni sulla symbol
Operazioni sulla symbol tabletable::
insert(s, t): ritorna l’indice della nuova entry per la stringa s, token t.
lookup(s): ritorna l’indice della entry per la stringa s, oppure 0 se la stringa non viene trovata.
Si può inizializzare la symbol table con le parole riservate:
Insert (“Div”, div)
esempio di implementazione:
esempio di implementazione:
ptr token attributi
0 1 2 3 4
div idid
D i v eos c o u n t eos i n c eos
function lexan
var lexbuf: array [1 . . 100] of char c: char
begin
while true do c := readchar
if c = ‘ ‘ or ‘tab’ then do nothing
else if c = newline then lineno := lineno + 1
else if isdigit (cc) then . . . . . .
return num
else if c “è una lettera”
then “metti cc e lettere e digit successivi in lexbuf”
“aggiorna la symbol table”
tokenval := il puntatore al lessema return il token id
else tokenval := NONE
return c (l’intero che codifica il carattere c) end
else if c = eof then return DONE
else if isalpha (c) then b := 0
while isalnum (c) do
lexbuf [b] := c c := readchar b := b + 1
if b >= BSIZE
then error (“errore di compilazione”) lexbuf [b] := eos
c := prechar
p := lookup (lexbuf)
if p = 0 then p := insert (lexbuf, id) tokenval := p
return symtable [p].token
Esempio
Esempio di di traduzionetraduzione
Tradurre in forma postfissa una sequenza di espressioni separate da ;
Le espressioni consistono di numeri, identificatori e degli operatori +, -, *, /, Div e Mod.
id rappresenta una sequenza non vuota di lettere e digit che iniziano con una lettera.
L’attributo lessema del token id dà la stringa di caratteri che formano il token.
L’attributo val del token num fornisce l’intero rappresentato da num.
list → E ; list list → ε
E → E + T E → E - T E → T
T → T * F T → T / F T → T div F T → T mod F T → F
F → ( E ) F → id
F → num
print (‘Mod’)
print (id.lessema) print (num.val) print (‘Div’) print (‘/’) print (‘+’)
print (‘*’) print (‘-’)
list → E ; list list → ε
E → T R’
R’ → + T R’ | - T R’
R’ → ε T → F R”
R” → * F R” | / F R”
R” → div F R”
R” → mod F R”
R” → ε F → ( E ) F → id
F → num list → E ; list
list → ε E → E + T E → E - T E → T
T → T * F T → T / F T → T div F T → T mod F T → F
F → ( E ) F → id
F → num
init init
symbol symbol
lexan lexan
parser parser
emitter emitter
error error
main
begin init parse
{termina con successo}
end
init: inizializza la symbol table con le keywordinit error
error: procedure error (m) print (lineno, m)
exit {termina senza successo}
lexan
lexan: analizzatore lessicale precedente
procedure parse begin
cc := lexan list
if cc = DONE then “successo”
end
list → E ; list { (, id, num}
list → ε {DONE}
procedure list
begin if cc = ‘(’ or cc = id or cc = num then cc := lexan
E
if cc = ‘;’ then cc := lexan
else error (“errore di sintassi”) list
else if cc = DONE then do nothing else error (“errore di sintassi”) end
procedure list
begin if cc = ‘(’ or cc = id or cc = num then cc := lexan
E
if cc = ‘;’ then cc := lexan
else error (“errore di sintassi”) list
else if cc =DONE then do nothing else error (“errore di sintassi”) end
procedure parse begin
cc := lexan list
if cc = DONE then “successo”
end
procedure parse begin
cc := lexan
while cc ≠ DONE do E
if cc = ‘;’ then cc := lexan
else error (“errore di sintassi”) {“successo”}
end
Gui(E → T R’) = {(, id, num} Gui(R’ → - T R’) = {-}
Gui(R’ → + T R’) = {+} Gui(R’ → ε ) = {;, )}
procedure E
begin if cc = ‘(’ or cc = id or cc = num then cc := lexan
T R’
else errore ( ) end
procedure R’
begin if cc = ‘+’ or ‘-’ then cc := lexan T
R’
else if cc = ‘;’ or cc = ) then do nothing else errore ( )
end
procedure E begin T
while (cc = ‘+’ or cc = ‘-’) do cc := lexan
T end
procedure T begin F
while (cc = ‘*’ or cc = ‘/’ or cc = div or cc = mod) do cc := lexan
F end
Gui(T → T R”) = {(, id, num} Gui(R” → div F R”) = {div}
Gui(R” → * F R”) = {*} Gui(R” → mod F R”) = {mod}
Gui(R” → / F R”) = {/} Gui(R” → ε) = {+, -, ;, )}
procedure F begin
if cc = ‘(’ then cc := lexan E
if cc = ‘)’ then cc := lexan
else error (“errore di sintassi”) else if cc = num then cc := lexan
else if cc = id then cc := lexan else error (“errore di sintassi”) end
Gui(F → (E) ) = { ( }
Gui(F → num ) = {num}
Gui(F → id ) = {id}
{print (‘Mod’)}
{print (id.lessema)}
{print (num.val)}
{print (‘Div’)}
{print (‘/’)}
{print (‘+’)}
{print (‘*’)}
{print (‘-’)}
list → E ; list list → ε
E → T R’
R’ → + T R’
R’ → - T R’
R’ → ε T → F R”
R” → * F R”
R” → / F R”
R” → div F R”
R” → mod F R”
R” → ε F → ( E ) F → id
F → num list → E ; list
list → ε E → T R’
R’ → + T R’
R’ → - T R’
R’ → ε T → F R”
R” → * F R”
R” → / F R”
R” → div F R”
R” → mod F R”
R” → ε F → ( E ) F → id
F → num
procedure E begin T
while (cc = ‘+’ or cc = ‘-’) do
cc := lexan T
end
emit (t, NONE) t := cc
var t
procedure T begin F
while (cc = ‘*’ or cc = ‘/’ or cc = div or cc = mod) do
cc := lexan F
end
emit (t, NONE) t := cc
var t
procedure F begin
if cc = ‘(’ then cc := lexan E
if cc = ‘)’ then cc := lexan
else error (“errore di sintassi”) else if cc = num then
cc := lexan else if cc = id then
cc := lexan else error (“errore di sintassi”) end
emit (num, tokenval) emit (id, tokenval)
procedure emit (t, tval) begin
if t = ‘+’ or t = ‘-’ or t = ‘*’ or t = ‘/’
then print (t)
else if t = div then print (Div) else if t = mod then print (Mod) else if t = num then print (tval)
else if t = id then print (symtable[tval].ptr) end
