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

Վիքիպեդիայից՝ ազատ հանրագիտարանից

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

Լեքսեմներ և թոքեններ[խմբագրել]

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

If var0 = 3.14 Then PrintLn( 'Pi' )

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

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

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

Սկզբունքը[խմբագրել]

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

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

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

Fsaid.png

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

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

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


Օրինակ[խմբագրել]

Java լեզվով գրված այս դասը նախատեսված է 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;
    }
}

Լեքսիկական անալիզատորների գեներատորներ[խմբագրել]

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