Analisi della sintassi: tipi di analisi del compilatore top down e bottom up

Il processo di analisi della sintassi nel design del compilatore segue la fase di analisi lessicale. È anche noto come albero di analisi o albero sintattico. L'albero di analisi è sviluppato con l'aiuto della grammatica predefinita del linguaggio. L'analizzatore di sintassi controlla anche se un dato programma soddisfa le regole implicite da una grammatica libera dal contesto. Se soddisfa, l'analizzatore crea l'albero di analisi di quel programma sorgente. Altrimenti, visualizzerà messaggi di errore.

Perché hai bisogno dell'Analizzatore di sintassi?

• Controlla se il codice è grammaticalmente valido
• L'analizzatore sintattico ti aiuta ad applicare regole al codice
• Ti aiuta ad assicurarti che ciascuna graffa di apertura abbia un saldo di chiusura corrispondente
• Ogni dichiarazione ha un tipo e il tipo deve esistere

Terminologia importante dell'analizzatore di sintassi

Terminologie importanti utilizzate nel processo di analisi della sintassi:

• Frase: Una frase è un gruppo di caratteri su un alfabeto.

• lessema: Un lessema è l'unità sintattica di livello più basso di una lingua (ad esempio, totale, inizio).

• Token: Un token è solo una categoria di lessemi.

• Parole chiave e parole riservate – È un identificatore che viene utilizzato come parte fissa della sintassi di un'istruzione. È una parola riservata che non è possibile utilizzare come nome di variabile o identificatore.

• Parole rumorose – Le parole non significative sono facoltative e vengono inserite in una frase per migliorare la leggibilità della frase.

• Commenti – È una parte molto importante della documentazione. Viene visualizzato principalmente da, /* */, o//Vuoti (spazi)

• Delimitatori – È un elemento sintattico che segna l'inizio o la fine di qualche unità sintattica. Come una dichiarazione o un'espressione, "inizio"..."fine" o {}.

• Set di caratteri – ASCII, Unicode

• Identificatori – È una restrizione sulla lunghezza che aiuta a ridurre la leggibilità della frase.

• Operasimboli – + e – esegue due operazioni aritmetiche di base.
• Elementi sintattici della Lingua

Perché abbiamo bisogno dell'analisi?

Un'analisi controlla anche che la stringa di input sia ben formata e, in caso negativo, la rifiuta.

Di seguito sono riportate le attività importanti eseguite dal parser nella progettazione del compilatore:

• Ti aiuta a rilevare tutti i tipi di errori di sintassi
• Trovare la posizione in cui si è verificato l'errore
• Descrizione chiara e accurata dell'errore.
• Recupero da un errore per continuare e trovare ulteriori errori nel codice.
• Non dovrebbe influenzare la compilazione dei programmi “corretti”.
• L'analisi deve rifiutare i testi non validi segnalando errori di sintassi

Tecniche di analisi

Le tecniche di parsing si dividono in due diversi gruppi:

• Analisi dall'alto verso il basso,
• Analisi dal basso

Analisi dall'alto

Nell'analisi top-down la costruzione dell'albero di analisi inizia dalla radice e poi procede verso le foglie.

Due tipi di analisi top-down sono:

1. Analisi predittiva:

L'analisi predittiva può prevedere quale produzione dovrebbe essere utilizzata per sostituire la stringa di input specifica. Il parser predittivo utilizza il punto look-ahead, che punta ai successivi simboli di input. Il backtracking non è un problema con questa tecnica di analisi. È noto come parser LL(1).

2. Analisi di discesa ricorsiva:

Questa tecnica di analisi analizza ricorsivamente l'input per creare un albero di prase. Consiste in diverse piccole funzioni, una per ogni non terminale della grammatica.

Analisi dal basso

Nell'analisi dal basso verso l'alto nella progettazione del compilatore, la costruzione dell'albero di analisi inizia con le foglie e quindi procede verso la radice. Viene anche chiamato analisi di riduzione del turno. Questo tipo di analisi nella progettazione del compilatore viene creato con l'aiuto dell'utilizzo di some strumenti software.

Errore: metodi di ripristino

Errori comuni che si verificano durante l'analisi del software di sistema

• Lessicale: nome di un identificatore digitato in modo errato
• sintattico: parentesi sbilanciata o punto e virgola mancante
• Semantico: assegnazione di valore incompatibile
• logico: Ciclo infinito e codice non raggiungibile

Un parser dovrebbe essere in grado di rilevare e segnalare qualsiasi errore trovato nel programma. Quindi, ogni volta che si verifica un errore, il parser dovrebbe essere in grado di gestirlo e continuare ad analizzare l'input rimanente. Un programma può avere i seguenti tipi di errori in varie fasi del processo di compilazione. Esistono cinque metodi comuni di recupero degli errori che possono essere implementati nel parser

Ripristino della modalità istruzione

• Nel caso in cui il parser riscontra un errore, ti aiuta a intraprendere azioni correttive. Ciò consente al resto degli input e degli stati di analizzare in anticipo.
• Ad esempio, l'aggiunta di un punto e virgola mancante avviene nel metodo di ripristino della modalità istruzione. Tuttavia, il progettista dell'analisi deve prestare attenzione mentre apporta queste modifiche poiché una correzione errata può portare a un ciclo infinito.

Recupero in modalità panico

• Nel caso in cui il parser incontri un errore, questa modalità ignora il resto dell'istruzione e non elabora l'input dall'input errato al delimitatore, come un punto e virgola. Questo è un semplice metodo di recupero degli errori.
• In questo tipo di metodo di recupero, il parser rifiuta i simboli di input uno alla volta finché non viene trovato un singolo gruppo designato di token di sincronizzazione. I token di sincronizzazione generalmente utilizzano delimitatori come o.

Recupero a livello di frase

• Il compilatore corregge il programma inserendo o eliminando token. Ciò gli consente di procedere all'analisi da dove si trovava. Esegue la correzione sull'input rimanente. Può sostituire un prefisso dell'input rimanente con una stringa che aiuta il parser a continuare il processo.

Produzioni di errori

• Il recupero della produzione di errori espande la grammatica per il linguaggio che genera i costrutti errati. Il parser esegue quindi la diagnostica degli errori su quel costrutto.

Correzione globale

• Il compilatore dovrebbe apportare il minor numero possibile di modifiche durante l'elaborazione di una stringa di input errata. Data la stringa di input a e la grammatica c errate, gli algoritmi cercheranno un albero di analisi per una stringa correlata b. Come alcuni inserimenti, cancellazioni e modifiche apportate ai token, necessarie per trasformare un in b è il meno possibile.

Grammatica

Una grammatica è un insieme di regole strutturali che descrivono una lingua. Le grammatiche assegnano la struttura a qualsiasi frase. Questo termine si riferisce anche allo studio di queste regole e questo file include morfologia, fonologia e sintassi. È in grado di descriverne molti, della sintassi di linguaggi di programmazione.

Regole della grammatica delle forme

• Il simbolo non terminale dovrebbe apparire a sinistra di almeno una produzione
• Il simbolo dell'obiettivo non dovrebbe mai essere visualizzato a destra di::= di qualsiasi produzione
• Una regola è ricorsiva se LHS appare nella sua RHS

Convenzioni Notazionali

Convenzioni di notazione il simbolo può essere indicato racchiudendo l'elemento tra parentesi quadre. È una sequenza arbitraria di istanze dell'elemento che può essere indicata racchiudendo l'elemento tra parentesi graffe seguite da un simbolo asterisco, { … }*.

Si tratta di una scelta dell'alternativa che può utilizzare il simbolo all'interno della regola unica. Può essere racchiuso tra parentesi ([,] ) quando necessario.

Due tipi di convenzioni notazionali sono Terminali e Non-terminali

1.Terminali:

• Lettere minuscole dell'alfabeto come a, b, c,
• Operao simboli come +,-, *, ecc.
• Simboli di punteggiatura come parentesi, cancelletto, virgola
• 0, 1, …, 9 cifre
• Stringhe in grassetto come id o if, qualsiasi cosa che rappresenti un singolo simbolo terminale

2.Non terminali:

• Lettere maiuscole come A, B, C
• Nomi in corsivo minuscolo: l'espressione o alcuni

Grammatica libera dal contesto

Una CFG è una grammatica ricorsiva a sinistra che ha almeno una produzione del tipo. Le regole in una grammatica libera dal contesto sono principalmente ricorsive. Un analizzatore di sintassi verifica che un programma specifico soddisfi o meno tutte le regole della grammatica libera dal contesto. Se soddisfa, questi analizzatori di sintassi delle regole possono creare un albero di analisi per quel programma.

expression -> expression -+ term
expression -> expression – term 
expression-> term
term  -> term * factor
term -> expression/ factor
term  -> factor factor
factor ->  ( expression )
factor -> id

Derivazione grammaticale

La derivazione grammaticale è una sequenza di regole grammaticali che trasforma il simbolo iniziale nella stringa. Una derivazione dimostra che la stringa appartiene al linguaggio grammaticale.

Derivazione più a sinistra

Quando la forma enunciale dell'input viene scansionata e sostituita nella sequenza da sinistra a destra, è nota come derivazione più a sinistra. La forma frasenziale che deriva dalla derivazione più a sinistra è chiamata forma frasenziale a sinistra.

Derivazione più a destra

La derivazione più a destra esegue la scansione e sostituisce l'input con le regole di produzione, in sequenza da destra a sinistra. È nota come derivazione più a destra. La forma frasenziale che deriva dalla derivazione più a destra è nota come forma frasenziale destra.

Sintassi vs. Analizzatore lessicale

Analizzatore di sintassi	Analizzatore lessicale
L'analizzatore della sintassi si occupa principalmente dei costrutti ricorsivi del linguaggio.	L'analizzatore lessicale facilita il compito dell'analizzatore sintattico.
L'analizzatore di sintassi funziona sui token in un programma sorgente per riconoscere strutture significative nel linguaggio di programmazione.	L'analizzatore lessicale riconosce il token in un programma sorgente.
Riceve input, sotto forma di token, da analizzatori lessicali.	È responsabile della validità di un token fornito da l'analizzatore di sintassi

Svantaggi dell'utilizzo degli analizzatori di sintassi

• Non determinerà mai se un token è valido o meno
• Not aiuta a determinare se un'operazione eseguita su un tipo di token è valida o meno
• Non puoi decidere che il token venga dichiarato e inizializzato prima di essere utilizzato

Sommario

• L'analisi sintattica è una seconda fase del processo di progettazione del compilatore che viene dopo l'analisi lessicale
• L'analizzatore sintattico ti aiuta ad applicare regole al codice
• Frase, lessema, token, parole chiave e parole riservate, parole non significative, commenti, delimitatori, set di caratteri, identificatori sono alcuni termini importanti utilizzati nell'analisi della sintassi nella costruzione del compilatore
• Parse controlla che la stringa di input sia ben formata e, in caso contrario, la rifiuta
• Le tecniche di parsing si dividono in due gruppi diversi: parsing top-down e parsing bottom-up
• Lessicale, sintattico, semantico e logico sono alcuni errori comuni che si verificano durante il metodo di analisi
• Una grammatica è un insieme di regole strutturali che descrivono una lingua
• Convenzioni di notazione il simbolo può essere indicato racchiudendo l'elemento tra parentesi quadre
• Una CFG è una grammatica ricorsiva a sinistra che ha almeno una produzione del tipo
• La derivazione grammaticale è una sequenza di regole grammaticali che trasforma il simbolo iniziale nella stringa
• L'analizzatore sintattico si occupa principalmente dei costrutti ricorsivi del linguaggio mentre l'analizzatore lessicale facilita il compito dell'analizzatore sintattico in DBMS
• Lo svantaggio del metodo dell'analizzatore di sintassi è che non determinerà mai se un token è valido o meno