Syntaktická analýza – Lexikální analyzátor

10.11.2018 · by Jan Smuda · in .NET, Programování

Minule jsem nakousnul problém algoritmického řešení výpočtu atomové hmotnosti chemické sloučeniny z jejího chemického vzorce. Uživatel vzorec někam zadá a program ho vyhodnotí. Aby to bylo možné, je potřeba nějakým způsobem zpracovat vstup od uživatele. První částí, která se zabývá zpracováním vstupního řetězce, je lexikální analýza. Jejím cílem je zkonstruovat lexikální analyzátor (lexer), který bude generovat seznam tokenů pro syntaktickou analýzu.

Série: Překladače a syntaktické analyzátory

Syntaktická analýza – Trocha teorie úvodem
Syntaktická analýza – Lexikální analyzátor
Syntaktická analýza – Bezkontextová gramatika
Syntaktická analýza – LL(1) parser

Lexikální analyzátor

Hlavním účelem lexikálního analyzátoru je přečtení vstupního textu a jeho převod na seznam tokenů. Abych to mohl udělat, musím mít nějaký formální popis formátu vstupního textu. K tomu mi obvykle poslouží definice jazyka, popisující jaká slova (lexémy) se v textu (v tomto případě chemický vzorec) mohou vyskytovat.

To ale není všechno. Také budu potřebovat výpočetní model, který dokáže načtené znaky ze vstupu zpracovat. Proto, že se často pohybuji v oblasti regulárních jazyků můžu k tomu použít konečný automat. Můžu samozřejmě použít i silnější výpočetní model, pokud mi to něco přinese.

Lexém

Lexém (nebo lexikální jednotka) je abstrakce všech tvarů nějakého slova. Tato abstrakce je reprezentována nějakým slovem tzv. lemma. Lemma je v podstatě zástupné slovo, které se používá ve slovnících (my programátoři používáme s oblibou výraz typ). V češtině je takovým lexémem např. hora. Slovo hora je lemma (zástupné slovo, reprezentují celou skupinu) a příklady lexému jsou hora, hory, horu atd. V programovacích jazycích může být lexémem např. řetězec reprezentující celé kladné číslo, reprezentované lemmatem Cislo a popsané regulárním výrazem [0-9]+ nebo \d+. Takový lexém pak může nabývat hodnot 0, 123, 55 atd. Lexém může mít klidně i jednu jedinou instanci slova. Např. lexém if, reprezentovaný lemmatem if s jedinou možnou hodnotou if.

Token

Token je objekt reprezentující nějaký lexém a jeho hodnotu. Obvykle se skládá z typu tokenu (lemma), konkrétní hodnoty slova a někdy i metadat. Když použiji příklad z předchozího odstavce pro celé kladné číslo, pak by takový token vypadal následovně <Cislo, 123, null>. Metadata nejsou třeba. V praxi by nejspíš tokenu číslo byly přiřazeny všechny varianty čísel (záporné, desetinné atd.) a pak by metadata mohly upřesňovat typ čísla.

Definice jazyka

Psal jsem, že potřebuji formální popis formátu vstupního textu. V lexikální analýze se jazyk často definuje pomocí sady regulárních výrazů, ke kterým se v tabulce přiřadí konkrétní typy tokenů. Může to vypadat třeba takto:

Typ tokenu	Regulární výraz	Neformální popis	Příklady lexémů
If	if	Klíčové slovo if	if
Id	[a-zA-Z]{1}\w+	Identifikátor	id1, id2, xy
RelOperator	[<>=!]=?	Relační operátor	!=, ==, <, <=, >, >=
Cislo	\d+	Celé kladné číslo	0123, 55

Princip činnosti lexikálního analyzátoru

Lexikální analyzátor čte sekvenčně vstupní text znak po znaku, a snaží se najít shodu načteného řetězce s regulárním výrazem v tabulce. V případě nalezení shody vyrobí nový token. Když lexikální analyzátor načte neznáme slovo, hlásí chybu. Existuje i možnost sestavit nějaký speciální typ tokenu pro slova, která nepatří do jazyka a vyhodnotit je až v době syntaktické analýzy. Lexikální analyzátor neřeší jestli posloupnost slov dává smysl! To je úkolem syntaktické analýzy. Důvodem oddělení lexikálního analyzátoru od syntaktického analyzátoru je hlavně zjednodušení konstrukce syntaktického analyzátoru.

Definice vstupní abecedy chemického vzorce

Protože se lexikální analyzátor implementuje jako konečný automat, není na škodu si zadefinovat i vstupní abecedu abych v tom měl jasno. V překladačích se často využívá lexikální analyzátor na odstranění komentářů, bílých znaků a všech věcí, které jsou sice povolné, ale pro překlad nejsou potřebné. To v mém případě nehrozí. Jakýkoliv znak, který nepatří do abecedy způsobí chybu, včetně bílých znaků. Při lexikální analýze chemického vzorce si, co se týče vstupní abecedy, vystačím se čtyřmi skupinami znaků.

Seznam povolených znaků (vstupní abeceda)
Typ znaku	Regulární výraz	Popis
SpecChar (SC)	^[\.\[\]]$	Speciální symboly závorky a oddělovače
Digit (S)	^[\d]$	Číslice
SmallLetter (SL)	^([a-z])$	Malá písmena
LargeLetter (LL)	^([A-Z])$	Velká písmena

Definice tokenů chemického vzorce

Seznam povolených typů tokenů bude trochu větší. V syntaktické analýze mi totiž nestačí vědět, jestli je token jen závorka. Pro syntaktickou analýzu již potřebuji závorky rozlišit podle toho, jestli jsou hranaté nebo kulaté, otevírací nebo zavírací. Je na zvážení, jestli rozlišovat závorky na úrovni tokenu nebo použít metadata. Můj jazyk je celkem jednoduchý, tak si můžu dovolit první variantu. V tokenech taky nemám typ Digit ale Number, protože číslo může být složeno z několika číslic.

Speciální případ je pak typ tokenu Symbol. Periodická soustava prvků povoluje symboly ve tvaru: velké písmeno následované žádným nebo max. dvěma malými písmeny. Jednotlivé symboly prvků musím mít tak jako tak někde v seznamu, protože uvedeným regulárním výrazem lze popsat pouze formát symbolu. Xxx mi regulárním výrazem projde, ale ještě se nejedná o symbol z periodické soustavy prvků. Zase je na zvážení, jestli toto rozhodování nechat na lexikálním analyzátoru nebo na některé z dalších komponent.

Seznam povolených slov (vstupní jazyk)
Typ tokenu	Regulární výraz	Popis
Separator	.	Oddělovače slouží v rovnici jako znak +
RoundBracketOpen	(	Kulatá otevírací závorka
RoundBracketClose	)	Kulatá zavírací závorka
SquareBracketOpen	[	Hranatá otevírací závorka
SquareBracketClose	]	Hranatá zavírací závorka
Number	^[\d]+$	Číslo
Symbol	^([A-Z]{1}[a-z]{0-2}])$	Symboly prvků.

Konstrukce konečného automatu

Algoritmus je jednoduchý. Pokud načtu nějaký SpecChar – mám kompletní slovo a můžu z něj vytvořit token. Pokud načtu číslici je nutné číst vstup tak dlouho, dokud bude na vstupu číslice. Protože ve vzorci může být něco jako H₁₂ a je jasné, že slova jsou tam dvě <H>, <12>. Pokud načtu písmeno musím číst vstup, dokud budu načítat malá písmena. Takto zase budu skládat symboly prvků. Např. Cn je jedno slovo <Cn> ale CN jsou dvě slova <C>, <N>.

Implementace pomocí rekurze

Implementovat se to dá různě např. pomocí rekurze. V takovém případě je potřeba číst jeden znak dopředu. O to se stará objekt IReaderUnit, který umí vrátit aktuální znak (funkce read) a má i funkci Peek, která poskytuje náhled na další znak v řadě, aniž by posunula counter a přečetla ho.

public interface IReaderUnit
{
	/// <summary>
	/// Look ahead to next character
	/// </summary>
	/// <returns>character or null</returns>
	char? Peek();

	/// <summary>
	/// Read string from input
	/// </summary>
	/// <returns>string or null</returns>
	char? Read();
}

public interface IReaderUnit

{

/// <summary>

/// Look ahead to next character

/// </summary>

/// <returns>character or null</returns>

char? Peek();

/// <summary>

/// Read string from input

/// </summary>

/// <returns>string or null</returns>

char? Read();

}

Také budu potřebovat někam nadefinovat moji abecedu a popis všech typů slov. K tomu jsem použil dva slovníky. Klíčem je typ znaku/slova a hodnotou je funkce, která na základě znaku/slova vrací, jestli odpovídá regulárnímu výrazu nebo ne. Funkci GetType pak předám mapovací slovník a znak/slovo a ona mi vrátí jeho typ. Pokud nepasuje na žádný typ pak vrací typ None.

public class LexAnalyzer : ILexAnalyzer<Token>
{
    ...
                   
    public LexAnalyzer(IReaderUnit readerUnit)
    {
        _readerUnit = readerUnit ?? throw new ArgumentNullException(nameof(readerUnit));

        _periodicTable = new PeriodicTableOfElements();

        _characterTable = new Dictionary<CharacterType, Func<char, bool>>();            
        _characterTable.Add(CharacterType.SpecChar, (c) => new Regex(@"^[\.\-\(\)\[\]]$").IsMatch(c.ToString()));
        _characterTable.Add(CharacterType.Digit, (c) => new Regex(@"^[\d]$").IsMatch(c.ToString()));            
        _characterTable.Add(CharacterType.SmallLetter, (c) => new Regex(@"^([a-z])$").IsMatch(c.ToString()));
        _characterTable.Add(CharacterType.LargeLetter, (c) => new Regex(@"^([A-Z])$").IsMatch(c.ToString()));

        _wordTable = new Dictionary<TokenType, Func<string, bool>>();                        
        _wordTable.Add(TokenType.Separator, (s) => new Regex(@"^[\.\-]$").IsMatch(s));
        _wordTable.Add(TokenType.RoundBracketOpen, (s) => s == "(");            
        _wordTable.Add(TokenType.RoundBracketClose, (s) => s == ")");
        _wordTable.Add(TokenType.SquareBracketOpen, (s) => s == "[");
        _wordTable.Add(TokenType.SquareBracketClose,(s) => s == "]");
        _wordTable.Add(TokenType.Number, (s) => new Regex(@"^[\d]+$").IsMatch(s));
        _wordTable.Add(TokenType.Symbol, IsSymbol);

        Tokens = new List<Token>();
    }
   
    private T GetType<T, X>(Dictionary<T, Func<X, bool>> table, X value)
    {
        foreach (var func in table)
        {
            if (func.Value(value))
            {
                return func.Key;
            }
        }

        return (T)Activator.CreateInstance(typeof(T));
    }
  
    ...

    public Token GetNextToken()
    {
        Token token = null;            
        char? curentChar = _readerUnit.Read();
        
        if (curentChar.HasValue)
        {
            _CurrentWord += curentChar.ToString();
            var currentType = GetType(_characterTable, curentChar.Value);

            if (currentType == CharacterType.Digit)
            {
                TryReadNext(CharacterType.Digit);
            }
            else if (currentType == CharacterType.LargeLetter ||
                     currentType == CharacterType.SmallLetter)
            {
                TryReadNext(CharacterType.SmallLetter);
            }                

            token = new Token(GetType(_wordTable, _CurrentWord), _CurrentWord);                
        }
        _CurrentWord = null;

        if (token != null)
        {
            Tokens.Add(token);
        }

        return token;
    }

    private void TryReadNext(CharacterType type)
    {            
        char? peekChar = _readerUnit.Peek();

        if (peekChar.HasValue && GetType(_characterTable, peekChar.Value) == type)
        {                                
            char? current = _readerUnit.Read();
            _CurrentWord += current.ToString();
            TryReadNext(type);                
        }            
    }                
}

public class LexAnalyzer : ILexAnalyzer<Token>

{

...

public LexAnalyzer(IReaderUnit readerUnit)

{

_readerUnit = readerUnit ?? throw new ArgumentNullException(nameof(readerUnit));

_periodicTable = new PeriodicTableOfElements();

_characterTable = new Dictionary<CharacterType, Func<char, bool>>();

_characterTable.Add(CharacterType.SpecChar, (c) => new Regex(@"^[\.\-\[\]]$").IsMatch(c.ToString()));

_characterTable.Add(CharacterType.Digit, (c) => new Regex(@"^[\d]$").IsMatch(c.ToString()));

_characterTable.Add(CharacterType.SmallLetter, (c) => new Regex(@"^([a-z])$").IsMatch(c.ToString()));

_characterTable.Add(CharacterType.LargeLetter, (c) => new Regex(@"^([A-Z])$").IsMatch(c.ToString()));

_wordTable = new Dictionary<TokenType, Func<string, bool>>();

_wordTable.Add(TokenType.Separator, (s) => new Regex(@"^[\.\-]$").IsMatch(s));

_wordTable.Add(TokenType.RoundBracketOpen, (s) => s == "(");

_wordTable.Add(TokenType.RoundBracketClose, (s) => s == ")");

_wordTable.Add(TokenType.SquareBracketOpen, (s) => s == "[");

_wordTable.Add(TokenType.SquareBracketClose,(s) => s == "]");

_wordTable.Add(TokenType.Number, (s) => new Regex(@"^[\d]+$").IsMatch(s));

_wordTable.Add(TokenType.Symbol, IsSymbol);

Tokens = new List<Token>();

}

private T GetType<T, X>(Dictionary<T, Func<X, bool>> table, X value)

{

foreach (var func in table)

{

if (func.Value(value))

{

return func.Key;

}

return (T)Activator.CreateInstance(typeof(T));

}

...

public Token GetNextToken()

{

Token token = null;

char? curentChar = _readerUnit.Read();

if (curentChar.HasValue)

{

_CurrentWord += curentChar.ToString();

var currentType = GetType(_characterTable, curentChar.Value);

if (currentType == CharacterType.Digit)

{

TryReadNext(CharacterType.Digit);

}

else if (currentType == CharacterType.LargeLetter ||

currentType == CharacterType.SmallLetter)

{

TryReadNext(CharacterType.SmallLetter);

}

token = new Token(GetType(_wordTable, _CurrentWord), _CurrentWord);

}

_CurrentWord = null;

if (token != null)

{

Tokens.Add(token);

}

return token;

}

private void TryReadNext(CharacterType type)

{

char? peekChar = _readerUnit.Peek();

if (peekChar.HasValue && GetType(_characterTable, peekChar.Value) == type)

{

char? current = _readerUnit.Read();

_CurrentWord += current.ToString();

TryReadNext(type);

}

Implementace pomocí zásobníku

Pokud bych se chtěl vykašlat na rekurzi, dalo by se to vyřešit přidáním zásobníku. Algoritmus by byl zhruba následující.

Dokud je na vstupu nějaký znak, přečti znak.
1. Pokud je znak závorka nebo oddělovač
  1. vyjmi všechny znaky ze zásobníku a udělej z nich token
  2. z načteného znaku udělej token
2. Pokud je znak číslice a
  1. na vrcholu zásobníku je něco jiného než číslice, pak vyjmi všechny znaky ze zásobníku a udělej z nich token
  2. vlož znak do zásobníku
3. Pokud je znak velké písmeno
  1. vyjmi všechny znaky ze zásobníku a udělej z nich token
  2. vlož znak do zásobníku
4. Pokud je znak malé písmeno a
  1. zásobník je prázdný nebo je na vrcholu číslice = chyba
  2. na vrcholu zásobníku je velké nebo malé písmeno, pak ulož znak na zásobník

PS: algoritmus jsem nezkoušel, ale tak nějak to zhruba bude.

Výstup lexeru

Výstupem lexeru je buď chyba nebo seznam tokenů, které vždy obsahují daný řetězec a typ tokenu. Pokud tedy narvu do lexeru chemický vzorec MgSO4.7(H2O) jako výstup bych měl dostat tokeny <Mg>, <S>, <O>, <4>, <.> , <7>, <(>, <H>, <2>, <O>, <)>.

Zdroje

https://cs.wikipedia.org/wiki/Lexik%C3%A1ln%C3%AD_anal%C3%BDza

https://cs.wikipedia.org/wiki/Lex%C3%A9m

https://wiki.cinstina.upol.cz/index.php/Lex%C3%A9m

Štítky: Algoritmy, Teoretická informatika

Syntaktická analýza – Lexikální analyzátor