Progettazione del compilatore - Espressioni regolari

L'analizzatore lessicale deve scansionare e identificare solo un insieme finito di stringhe / token / lessemi validi che appartengono alla lingua in mano. Cerca il modello definito dalle regole della lingua.

Le espressioni regolari hanno la capacità di esprimere linguaggi finiti definendo un modello per stringhe finite di simboli. La grammatica definita dalle espressioni regolari è nota comeregular grammar. La lingua definita dalla grammatica regolare è nota comeregular language.

L'espressione regolare è una notazione importante per specificare i modelli. Ogni modello corrisponde a un insieme di stringhe, quindi le espressioni regolari servono come nomi per un insieme di stringhe. I token del linguaggio di programmazione possono essere descritti da linguaggi normali. La specifica delle espressioni regolari è un esempio di definizione ricorsiva. Le lingue normali sono facili da capire e hanno un'implementazione efficiente.

Ci sono un certo numero di leggi algebriche che sono obbedite dalle espressioni regolari, che possono essere usate per manipolare le espressioni regolari in forme equivalenti.

Operazioni

Le varie operazioni sulle lingue sono:

• L'unione di due lingue L e M è scritta come

  LUM = {s | s è in L oppure s è in M}

• La concatenazione di due lingue L e M è scritta come

  LM = {st | s è in L e t è in M}

• La chiusura di Kleene di una lingua L è scritta come

  L * = zero o più occorrenze della lingua L.

Notazioni

Se r e s sono espressioni regolari che denotano i linguaggi L (r) e L (s), allora

• Union : (r) | (s) è un'espressione regolare che denota L (r) UL (s)

• Concatenation : (r) (s) è un'espressione regolare che denota L (r) L (s)

• Kleene closure : (r) * è un'espressione regolare che denota (L (r)) *

• (r) è un'espressione regolare che denota L (r)

Precedenza e associatività

• *, concatenazione (.) e | (segno di tubo) sono associativi a sinistra
• * ha la precedenza più alta
• La concatenazione (.) Ha la seconda precedenza più alta.
• | (segno di pipa) ha la precedenza più bassa di tutte.

Rappresentare i token validi di una lingua in un'espressione regolare

Se x è un'espressione regolare, allora:

• x * significa zero o più occorrenze di x.

  cioè, può generare {e, x, xx, xxx, xxxx, ...}

• x + indica una o più occorrenze di x.

  ovvero può generare {x, xx, xxx, xxxx ...} o xx *

• X? significa al massimo un'occorrenza di x

  cioè, può generare {x} o {e}.

[az] sono tutti alfabeti minuscoli della lingua inglese.

[AZ] è tutto alfabeti maiuscoli della lingua inglese.

[0-9] sono tutte le cifre naturali utilizzate in matematica.

Rappresentare l'occorrenza di simboli utilizzando espressioni regolari

lettera = [a - z] o [A - Z]

cifra = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 o [0-9]

segno = [+ | -]

Rappresentazione di token di lingua utilizzando espressioni regolari

Decimale = (segno) ^? (cifra) ⁺

Identificatore = (lettera) (lettera | cifra) *

L'unico problema rimasto con l'analizzatore lessicale è come verificare la validità di un'espressione regolare utilizzata nello specificare i modelli di parole chiave di una lingua. Una soluzione ben accettata è quella di utilizzare automi finiti per la verifica.