Lexical analysis

Lexicale Analyse
Compilerconstructie: Deel 1
Matthias Moulin
2e Master CW‐MMC
7 Oktober 2014
1
Inhoud
• Situering
•
•
•
•
•
•
•
•
•
•
•
Terminologie
Formele talen
Reguliere expressies
Ambiguïteiten
Deterministische Eindige Toestandsautomaten
Error handling
Niet‐Deterministische Eindige Toestandsautomaten
Equivalentie van NFAs en DFAs
Minimalisatie van DFAs
Equivalentie van REs en FAs
Lexicale analyse generators
• Examenvragen
• Bibliografie
2
Situering
Lexicaal
• Gerelateerd aan woorden of de woordenschat van een taal
• Staat los van de grammatica en constructie van die taal
3
Situering
Source language ‐> Target language
1. Begrijpen van structuur en betekenis 2. Op een andere manier in elkaar steken/genereren
(Source)
(Target)
Ruwweg 2 fasen
1. Analyse
1.
2.
3.
Lexicale analyse
Syntax analyse
Semantische analyse
broncode ‐> individuele woorden of tokens
zinstructuur van programma parsen
de betekenis van programma achterhalen
2. Synthese
4
Situering
5
Lexicale Tokens
Definitie (Lexicale Token) Een sequentie van karakters die als ondeelbaar beschouwd wordt in de grammatica van de programmeertaal.
‐> programmeertaal categoriseert deze in eindige set van Tokentypes
VBn:
Reserved keyword voor sommige programmeertalen
6
Lexicale Tokens
VBn van niet‐lexicale tokens afhankelijk van de toepassing*
• Worden wel beschreven en gescand, maar worden niet doorgegeven aan de parser. (hebben geen tokentype)
• De parser white space en comments in rekening laten nemen op elk mogelijk ogenblik, zou deze overmatig complex maken.
*Lexical analysers lexers worden niet enkel door compilers gebruikt. Bv.: In een automatisch refactoring systeem moet commentaar ook in rekening gebracht worden.
7
Lexicale Tokens – Macro’s
Macro processing
Characterstream 1
Preprocessing
Characterstream 2
Lexical analysis
Tokens
Lexical Analyser
Characterstream 1
Lexical analysis + macro processing
Tokens
Lexical Analyser
Synoniemen: Lexical Analyser
Lexer
8
Lexicale Tokens
VB:
Returned stream:
FLOAT ID(match0) LPAREN CHAR STAR ID(s) RPAREN
LBRACE IF LPAREN BANG ID(strncmp) LPAREN ID(s) COMMA STRING(0.0) COMMA NUM(3) RPAREN RPAREN RETURN REAL(0.0) SEMI RBRACE EOF
Semantische waarden: deze geven additionele informatie bij het tokentype
9

Lexicale Tokens gaan we specifiëren d.m.v.
reguliere expressies
Lexers gaan we implementeren d.m.v. deterministische eindige toestandsautomaten
10
Terminologie
Een set S is een collectie van objecten
De powerset
van een set is set van alle subsets van .
Stel ∈ en , … , zijn om het even welke objecten, dan is ( , … , ) een (geordend) ‐tuple
Stel , … , zijn sets, dan is het cartesische product de set van alle ‐tuples ( , … , )
waarbij ∈ voor ∈ 1, …
⋯
11
Formele Talen
Het alfabet Σ, is een eindige set van symbolen/karakters.
Een string is een eindige sequentie van symbolen uit een alfabet Σ.
De lege string is (“”).
De set van alle mogelijke strings over een alfabet Σ is Σ ∗ .
Een taal over een alfabet Σ: ⊆ Σ ∗ .
Gegeven een string en een taal , is in ?
Als Σ
Als Σ
∅ dan is Σ ∗ oneindig aftelbaar (alle strings over Σ)
∅ dan is Σ ∗ oneindig overaftelbaar (alle talen over Σ)
12
Formele Talen
Klassen van talen
Recursief‐enumereerbare talen
Context‐sensitieve talen
Context‐vrije talen
Reguliere talen
Minimale automaat om talen te herkennen Turing Machine
Lineair begrensde automaat
Niet‐deterministische stapelautomaat
Eindige toestandsautomaat
13
Formele Talen
Klassen van talen
Reguliere talen
Minimale automaat om talen te herkennen Eindige toestandsautomaat
Definitie (Reguliere Taal) Een taal is regulier ⟺ deze taal wordt beschreven door een reguliere expressie
⟺ deze taal wordt herkend door een eindige toestandsautomaat
14
Reguliere Expressies
Definitie (Reguliere Expressie) is een reguliere expressie RE als van de volgende vorm is:
1. a voor een ∈ Σ
2.
3. ∅
4.
|
5.
.
∗
6.
) ) waarbij waarbij waarbij beschrijft ∈ Σ ∗
en reguliere expressies zijn
en reguliere expressies zijn
eenreguliere expressie is (unie)
(concatenatie)
(Kleene‐ster)
(notatie: 15
Reguliere Expressies
.
≡
∗ ≡
≡
?≡ |
≡ |
0
∗
≡
…
≡ a|b|c| … x y|z
≡
…
≡ABC… XYZ
9 ≡ 012 … 789 ≡ 0|1|2| … 7 8|9
. staat voor één enkel karakter behalve een nieuwe lijn
“a.+” staat letterlijk voor de string a.+
Operatorprioriteiten: * . |
16
Reguliere Expressies
:
Te ondernemen actie voor de parser
9
{ return IF; }
{ return ID; }
{ return NUM; }
{ return REAL; )
{ /* do nothing */ }
0
0
9
∗
0 9 “.” 0 9 ∗ | 0 9 ∗ “.” 0
“‐‐”[a‐z]*“\n” | “ ” | “\n” | “\t”
.
9
lexicale specificatie moet compleet zijn
{ error(); }
17
Ambiguïteiten
Regel (Longest match)
De langste initiële substring van de input die door een RE beschreven wordt, wordt genomen als volgende token.
•
Bv.: “if8” matcht als identifier
Regel (Rule priority)
De langste initiële substring van de input die als eerste beschreven wordt door een RE, bepaalt het tokentype.
• Volgorde van RE regels is van belang
•
Bv.: “if”matcht als reserved word
18
Reguliere expressies zijn statisch en declaratief
Hoe moeten reguliere expressies geïmplementeerd worden?
Automaten zijn dynamisch en imperatief
19
Deterministische Eindige Toestandsautomaten
Definitie (Deterministische Eindige Toestandsautomaat) Een deterministische eindige toestandsautomaat (DFA) is een 5‐tuple , Σ, , , waarbij
1.
is een eindige set
de toestanden
2. Σ is een eindige set
het alfabet
3. : Σ →
de transitiefunctie
4.
∈
de start/initiële toestand
5. : →
de actiefunctie
∈ |
∅
de set met de accepterende/finale toestanden
20
Deterministische Eindige Toestandsautomaten
Merk op dead/garbage state ∉
is niet vermeld
21
Deterministische Eindige Toestandsautomaten
DFA
, Σ, , , en … ∶ ∀ ∈ Σ met ∈ 1, …
Dan accepteert Als er een sequentie van toestanden , , … , in bestaat die voldoet aan:
1.
en
2.
,
voor ∈ 1, …
1 en
3.
∈
∈ |
∅
S
Dan
Als
herkent ∈ Σ ∗ (notatie: | 22
Mogelijke encodering van DFA via lookup tabellen
• Transitiematrix ∶
Σ→
Dead state
Initiële toestand
• Finality array ∶
→
23
DFA ‐ Variabelen
• DFApositie
Longest match
• Toestandsnummer van de meest recentste finale toestand (1)
• Positie van de input op de meest recentste finale toestand (2)
Wanneer een finale toestand bereikt wordt
‐> variabele updaten
Wanneer dead state bereikt wordt
‐> token gekend (1)
‐> eindpositie gekend (2)
24
25
Error handling
• lexicale specificatie moet compleet zijn
.
{ error(); }
Wanneer dead state bereikt wordt
Toestandsnummer v/d meest recentste finale toestand
dead state
• error()
Print een error message rechtstreeks vanuit de lexer.
/
Return ‘iets’ aan de parser (of via gedeelde datastructuur, via globale variabelen). De parser moet de juiste errorproducties hebben om de error af te handelen en eventueel van de error op de gepaste manier te recoveren. Dit heeft het voordeel alle error handling in de parser uit te voeren.
26
Niet‐Deterministische Eindige Toestandsautomaten
Definitie (Niet‐Deterministische Eindige Toestandsautomaat) Een niet‐deterministische eindige toestandsautomaat (NFA) is een 5‐tuple , Σ, , , waarbij
1.
is een eindige set
de toestanden
2. Σ is een eindige set
het alfabet
3. : Σ →
)
de transitiefunctie
4.
∈
de start/initiële toestand
5. : →
de actiefunctie
∈ |
Notatie: Σ
∅
Σ∪
de set met de accepterende/finale toestanden
27
Niet‐Deterministische Eindige Toestandsautomaten
S NFA
, Σ, , , , en … ∶∀ ∈ Σ
met ∈ 1, …
Dan accepteert Als er een sequentie van toestanden , , … , in bestaat die voldoet aan:
1.
en
2.
∈
,
voor ∈ 1, …
1 en
3.
∈
∈ |
∅
Dan
Als
herkent ∈ Σ ∗ (notatie: | 28
DFAs zijn gemakkelijk te implementeren als computerprogramma’s
1: Procedure NextToken()
2: While true do
3: Consumeer volgende karakter van inputstring
4:
Voer default actie uit
4: Bepaal nieuwe huidige toestand op basis van transitietabel
5: If huidige toestand is dead state
6:
then bepaal token en eindpositie; voer bijhorende actie uit
7: If huidige toestand is finale toestand
8:
then update longest‐match variabelen
NFAs zijn moeilijker te implementeren omdat computers geen goede “gok” hardware hebben
Gelukkig is het altijd mogelijk om een NFA naar een equivalente DFA te converteren
29
Equivalentie van NFAs en DFAs
Theorema NFAs en DFAs beschrijven dezelfde klasse van talen
Lemma 1: ∀DFA :∃NFA • Bewijs: Elke DFA is ook een NFA volgens de definitie van NFAs
Lemma 2: ∀NFA :∃DFA • Bewijs: zie volgende slide
30
Subsetconstructie
Lemma 2: ∀
:∃
Bewijs: stel NFA
, Σ, , ,
construeer DFA D
volgt:
1.
)
2.
3.
,
⋃ ∈
})
, Σ,
,
,
, ′ met als of ⋃ ∈
of } ,
Notatie:
| kanbereiktwordenvanuiteen ∈
via0ofmeerdere transities
31
Subsetconstructie
Lemma 2: ∀
:∃
Bewijs: stel NFA
, Σ, , ,
, Σ,
construeer DFA D
volgt:
5.
Als ∈ ∩ ′ ∧
Anders lege actie
Met ∈ |
,
, ′ met als ∀ ∈
∅
∩
:
Rule Priority
32
Rule Priority
Merk op dead/garbage state ∉
is niet vermeld
33
Subsetconstructie
Deomzettingkanperkarakter,datgeconsumeerdwordt
tijdensdelexicaleanalyse,uitgevoerdworden.
‐ Hetmanipulerenvansetsvantoestandenisduur
‐ NFAeerstomzettennaarDFA
34
Subsetconstructie ‐ Complexiteit
)
‐ Als NFA toestanden heeft, kan equivalente DFA tot 2
toestanden hebben (worst case).
Hier zitten meestal veel onbereikbare (vanuit starttoestand) toestanden bij.
Worst‐case # ′
Θ Σ ∗2
35
Subsetconstructie via breadth‐first transitiegraaf
1: 0 ← ;
1 ←
2:max_
_
← 1; ←0
3:
max_
_
4:
foreach
∈Σ
,
5:
′
6:
if max_
_
7: then
,
←
8: else
max_
_
← max_
_
9:
max_
_
←
,
← max_
10:
11:
←
1
1
_
36
Minimalisatie van een DFA Minimalisatieproces:
1. Verwijder ontoegankelijke toestanden
2. Combineer “equivalente” toestanden
37
Minimalisatie van een DFA Gegeven: DFA
Definieer: : , Σ, ,
Σ∗ →
,
als
,
,
,
Equivalentierelatie:
∀ ∈ Σ∗ :
,
,
,
Equivalentieklassen onder ≈:
|
38
Quotiëntconstructie
Stel DFA
, Σ, ,
Definieer: DFA D/ als volgt:
1.
| ∈
2.
,
,
3.
4.
,
, Σ,
,
, ′
quotiënt automaat
′
Stelling:L D/
• Bewijs: zie [Clarke]
Stelling: D/ heefteenminimaalaantaltoestanden
39
Minimalisatiealgoritme
1. Schrijf alle paren , met , ∈ ∧
initieel niet gemarkeerd
2. Markeer , als of andersom
3. Herhaal tot er geen wijzigingen meer gebeuren:
– Als er een niet‐gemarkeerd paar , bestaat waarbij , ,
,
is gemarkeerd voor een ∈ Σ, markeer dan , .
Postconditie: ⇔ , is niet gemarkeerd
• Bewijs: zie [Clarke]
40
Minimalisatiealgoritme ‐ Complexiteit
Moore’s algoritme
Worst‐case #iteraties
2
1
!
2 !
2
1
1
2
1
Θ
Worst‐case #checks
Σ ∗
1
2
2
⋯
1
0
Θ Σ ∗
checks/paar
Met
#toestandenorigineleDFA
41
Minimalisatiealgoritme ‐ Complexiteit
Moore’s algoritme
Average‐case #checks
Σ ∗ Σ ∗ log log
*
Hopcroft’s algoritme
Worst‐case #checks
Σ ∗ Average‐case #checks
Σ ∗ Σ ∗ log log
*
Afhankelijkvanderandomdistributievandeautomatendiegebruiktwordenom
deaverage‐casegedragtemodelleren.
42
Equivalentie van REs en FAs
Theorema REs en FAs (DFAs, NFAs) beschrijven dezelfde klasse van talen
Lemma 1: ∀RE :∃NFA • Bewijs: zie volgende slide
Lemma 2: ∀DFA :∃RE • Bewijs: zie [Clarke]
43
Lemma 1: ∀RE : ∃ NFA
• Bewijs: d.m.v. inductie op de structuur van R
1. R = a voor een ∈ Σ
–
–
,
,
met , Σ, ,
,
en met ,
∅ voor ∧
2.
, Σ, , ,
,
∅
–
– met 3.
∅
, Σ, , , ∅ met ,
∅
–
– met 4.
5.
6.
met |
.
) waarbij ) waarbij en
en
reguliere expressies zijn
reguliere expressies zijn
∗
waarbij eenreguliere expressie is
REs zijn gesloten onder unie, concatenatie en kleene‐star
□
Merk op: Abstractie van de acties gemaakt voor
44
45
The Big Math Picture
Lexicale analyse
Lexicale Specificatie (o.a. REs)
NFA
Rule Priority
DFA
Minimale DFA
Longest Match
46
Lexicale analyse generators
Lexicale Specificatie
Lexicale analyse generatie
Lexical Analyse Generator
Characterstream
DFA
Bv.: C‐Program
Lexical Analyser
Lexical analysis
Tokens
Eigenlijk is een lexicale analyse generator ook een compiler
47
Lexicale analyse generators ‐ Input
Lexicale specificatie (Lex specifiek)
1. Definitie
Macros en headers (onveranderd gekopieerd)
2. Regels
1 RE met bijhorende actie
3. C‐code
Overige C‐code (Bv.: calls via acties)
Actie communiceert tokentype (en bijhorende semantische waarden) aan Parser.
48
Lexicale analyse generators ‐ Input
Lexicale specificatie (Lex specifiek)
%{
#include “tokens.h”
Definitie
#include “errormsg.h”
union {int ival; string sval; double fval; } yylval;
Global variabele voor parser
int charPos=1
#define ADJ (EM_tokPos=charPos, charPos+=yyleng)
%}
Parser gebruikt dit voor syntax error messages
digits
[0‐9]+
%%
if
[a‐z][a‐z0‐9]*
{digits}
({digits}“.”[0‐9]*)|([0‐9]*“.”{digits})
(“‐‐”[a‐z]*“\n”)|(“ ”|“\n”|“\t”)+
.
+ Rule Priority
Regels
{ADJ; return IF; }
{ADJ; yylval.sval=String(yytext); return ID; }
{ADJ; yylval.ival=atoi(yytext); return NUM; }
{ADJ; yylval.fval=atof(yytext); return REAL; }
integer
{ADJ; }
{ADJ; EM_error(“illegal character”); }
49
Lexicale analyse generators ‐ Output
• Transitietabel
‐> programma dat dit interpreteert
• Een programma met (of ) statements
= partiële evaluatie van het algemene programma dat een transitietabel interpreteert t.o.v. een gegeven (gegenereerde) transitietabel
Vbn:
C
• Lex (meestal in combinatie met parsergenerator Yacc)
• Flex (“fast lexical analyser”)
C++
• Flex++
Java
• JavaCC
• SableCC
50
The Big Picture
Characterstream
Lexicale analyse generatie
Lexicale Specificatie (o.a. REs)
NFA
Rule Priority
Lexicale analyse
DFA
Minimale DFA
Longest Match
Tokens
51
Examenvragen
• Bespreek de werking van een Lexicale Analyser en situeer deze functionele module in de architectuur van de compiler.
• Wat is de functie van een Lexicale Analyser Generator en wat is het verband tussen deze generator en REs, NFAs, DFAs en Lexers?
• Leg de begrippen “longest‐match” en “rule priority” uit. Waarom worden ze gebruikt in de lexicale analyse? Hoe worden ze geïmplementeerd?
• Hoe verloopt de error handling in de lexicale analyse?
52
Bibliografie
Andrew Appel
Modern Compiler Implementation in C, Cambridge University Press, 2nd Edition, 2004
Andrew Appel
Modern Compiler Implementation in Java, Cambridge University Press, 2nd Edition, 2004
Daniel P. Friedman and Mitchell Wand
Essentials of programming languages, The MIT Press 3th edition, 2008
Dave Clarke
Fundamentals of Computer Science, Januari 2014
53
54

Download Report