Լեքսիկական վերլուծություն

Լեքսիկական վերլուծությունը (լեքսիկական անալիզ) կոմպիլյացիայի փուլերից մեկն է (սովորաբար առաջինը), որի նպատակն է մուտքային հոսքը կտրատել լեքսեմների և ամեն մեկին համապատասխանեցնել որոշակի թոքեն։

Լեքսեմներ և թոքեններ

Դիցուք տրված է Պասկալ լեզվով գրված հետևյալ օրինակը.

If var0 = 3.14 Then PrintLn( 'Pi' )

Լեքսիկական անալիզատորն իր աշխատանքի արդյունքում շարահյուսական անալիզատորի համար կկառուցի հետևյալ աղյուսակին համարժեք աղյուսակ.


Լեքսեմ	Թոքեն
If	Ծառայողական բառ "if"
var0	Իդենտիֆիկատոր
=	Գործողություն "հավասար է"
3.14	Իրական թիվ
Then	Ծառայողական բառ "then"
PrintLn	Իդնտիֆիկատոր
(	Բացվող փակագիծ
'Pi'	Տող
)	Փակվող փակագիծ

Այլ կերպ ասած, լեքսեմը դա տողի այն կտորն է, որ ճանաչել է լեքսիկական անալիզատորը, իսկ թոքենը լեքսեմին համապատասխանեցված տիպն է։

Սկզբունքը

Սովորաբար լեքսիկական վերլուծության առաջին փուլը հիմնված է վերջավոր ավտոմատի գաղափարի վրա։ Օրինակ, եթե իդենտիֆիկատերները նկարագրվում են

[[:alpha:]][[:alnum:]]*

կանոնավոր արտահայտությամբ, և դրան նկարագրող վերջավոր ավտոմամտի ուրվապատկերն է.

ապա իդենտիֆիկատորները մուտքային հոսքում տարբերելու համար կարելի է գրել բերված ավտոմատի հետևյալ իրականացումը.

// ...
if( isalpha(ch) ) {
    lexem = "";
    while( isalpha(ch) || isdigit(ch) ) {
        lexem += ch;
        ch = readChar();
    }
    unReadChar();
    return IDENT;
}
// ...

Նույն կերպ մոդելավորվում են նաև այլ լեքսիկական կառուցվածքներ ներկայացնող կանոնավոր արտահայտությունները (վերջավոր ավտոմատները)։

Օրինակ

Ջավա լեզվով գրված այս դասը նախատեսված է Oberon-0 լեզվի լեքսիկական վերլուծության համար։

import java.io.File;
import oberonzero.parser.Token;

/**
 */
public class OberonScanner {
    // Ծառայողական բառերի ցուցակ
    private static final String[] keywords = { "MODULE", "BEGIN", "END",
        "PROCEDURE", "CONST", "TYPE", "VAR", "RECORD", "ARRAY",
        "OF", "WHILE", "DO", "IF", "THEN", "ELSIF", "ELSE",
        "DIV", "MOD", "AND", "OR", "BOOLEAN", "INTEGER" };

    // source to scan
    private char[] source;
    private int pos, lineno;
    private String tokval;

    /***/
    public void setTextToScan(String src)
    {
        source = src.concat("\n").toCharArray();
        pos = 0;
        lineno = 1;
    }

    /** Լեքսեմ */
    public String tokenValue()
    { return tokval; }

    /** Ընթերցվող տողի համարը */
    public int lineNumber()
    { return lineno; }

    /** Հիմնական պրոցեդուրա */
    public Token nextToken()
    {
        // անտեսել բացատանիշերը
        while(source[pos] == ' ' || source[pos] == '\t' || source[pos] == '\n') {
            if(source[pos] == '\n') ++lineno;
            ++pos;
            // ֆայլի (հոսքի) ավարտ
            if( pos >= source.length )
                return Token.lxmEof;
        }

        // Կարդալ թիվ
        if(Character.isDigit(source[pos])) {
            tokval = String.valueOf(source[pos++]);
            while(Character.isDigit(source[pos])) {
                tokval += String.valueOf(source[pos]);
                ++pos;
            }
            return Token.lxmNumber;
        }

        // Կարդալ իդենտիֆիկատոր կամ ծառայողական բառ
        if(Character.isLetter(source[pos])) {
            tokval = String.valueOf(source[pos++]);
            while(Character.isLetter(source[pos]) || Character.isDigit(source[pos])) {
                tokval += String.valueOf(source[pos]);
                ++pos;
            }
            return keyWord(tokval);
        }
        
        return metaSymbol();
    }

    /***/
    private Token metaSymbol()
    {
        char ch = source[pos++];
        if(ch == '(') return Token.lxmLeftPar;
        if(ch == ')') return Token.lxmRightPar;
        if(ch == '[') return Token.lxmLeftBracket;
        if(ch == ']') return Token.lxmRightBracket;
        if(ch == '+') return Token.lxmPlus;
        if(ch == '-') return Token.lxmMinus;
        if(ch == '*') return Token.lxmAsterisk;
        if(ch == '/') return Token.lxmSlash;
        if(ch == '&') return Token.lxmAmpersand;
        if(ch == '~') return Token.lxmTilde;
        if(ch == ',') return Token.lxmComma;
        if(ch == '.') return Token.lxmDot;
        if(ch == '=') return Token.lxmEqual;
        if(ch == '#') return Token.lxmNotEqual;
        if(ch == '>') {
            if(source[pos++] == '=')
                return Token.lxmGreatEqual;
            --pos;
            return Token.lxmGreat;
        }
        if(ch == '<') {
            if(source[pos++] == '=')
                return Token.lxmLessEqual;
            --pos;
            return Token.lxmLess;
        }
        if(ch == ':'){
            if(source[pos++] == '=')
                return Token.lxmAssign;
            --pos;
            return Token.lxmColon;
        }
        if(ch == ';')
            return Token.lxmSemicolon;

        return Token.lxmAny;
    }

    /***/
    private static Token keyWord(String str)
    {
        boolean found = false;
        for(String s : keywords)
            if(s.equals(str.toUpperCase())) {
                found = true;
                break;
            }
        if(found) {
            String s0 = "lxm" + str.charAt(0);
            s0 = s0.concat(str.substring(1).toLowerCase());
            return Token.valueOf(s0);
        }
        return Token.lxmIdentifier;
    }
}

Լեքսիկական անալիզատորների գեներատորներ

Ծրագրավորման գործում արագ և հուսարլի լեքսիկական անալիզատորներ ստեղծվում են հենց այդ նպատակի համար նախատեսված գեներատերների միջոցով։ Առավել մեծ տարածում ունի Յունիքս համամակարգի համար մշակված Lex գործիքը։