문법 분석

필기 문법 분석은 귀속 하강 분석법과 산자 우선 분석법을 사용한다.

BNF

문법 분석은 상하문에 대해 문법과 무관하다.정의할 때 일반적으로 BNF로 설명됩니다.lua의 BNF는 대체로 다음과 같습니다.

chunk ::= block

block ::= {stat [";"]}

stat ::=
     "do" block "end" |
     "while" exp "do" block "end" |
     "if" exp "then" block {"elseif" exp "then" block} ["else" block] "end" |
     "for" Name "=" exp "," exp ["," exp] "do" block "end" |
     "for" namelist "in" explist "do" block "end" |
     "function" funcname funcbody |
     "local" "function" Name funcbody |
     "local" namelist ["=" explist] |
     "return" [explist] |
     "break" |
     varlist "=" explist |
     Name {tableindex | funccall} funccall

namelist ::= Name {"," Name}

varlist ::= var {"," var}

var ::= Name [{tableindex | funccall} tableindex]

funcname ::= Name {"." Name} [":" Name]

funcbody ::= "(" [parlist] ")" block "end"

parlist ::= Name {"," Name} ["," "..."] | "..."

explist ::= {exp ","} exp

tableconstructor ::= "{" [fieldlist] "}"

fieldlist ::= field {fieldsep field} [fieldsep]

field ::= "[" exp "]" "=" exp | Name "=" exp | exp

fieldsep ::= "," | ";"

exp ::= mainexp | exp binop exp

mainexp ::= nil | false | true | Number | String |
     "..." | function | tableconstructor |
     prefixexp |
     unop exp|

function ::= "function" funcbody

prefixexp ::= (Name | "(" exp ")") {tableindex | funccall}

tableindex ::= "[" exp "]" | "." Name

funccall ::= args | ":" Name args

args ::=  "(" [explist] ")" | tableconstructor

binop ::= "+" | "-" | "*" | "/" | "^" | "%" | ".." |
     "" | ">=" | "==" | "~=" |
     "and" | "or"

unop ::= "-" | "not" | "#"

이 문법 정의는 정리를 거쳐 손으로 해석기에 편리하다.

귀속 하강 해석

귀속 하강 분석법은 일반적인 문장을 처리하는 데 쓰인다.위의 BNF는 특수한 설계를 거쳐 두 개의 접두사 단어를 읽으면 어떤 해석 함수를 선택할지 확정할 수 있으며 LL(2) 문법이라고 할 수 있다.코드 구현은 비교적 무뇌하다. 차이가 많지 않은 것은 BNF 문장이 하나의 해석 함수와 하나의 문법 트리 결점 유형에 대응하는 것이다.접두사 단어를 읽고 어떤 해석 함수를 선택해야 하는지 보십시오.
stat를 예로 들면 위조 코드

Block ParseBlock()
{
    var block = new Block();
    for (; ; )
    {
        SyntaxTree statement = null;
        var token_ahead = LookAhead();
        switch (token_ahead.m_type)
        {
            case (int)';':
                NextToken(); continue;
            case (int)TokenType.DO:
                statement = ParseDoStatement(); break;
            case (int)TokenType.WHILE:
                statement = ParseWhileStatement(); break;
            case (int)TokenType.IF:
                statement = ParseIfStatement(); break;
            case (int)TokenType.FOR:
                statement = ParseForStatement(); break;
            case (int)TokenType.FOREACH:
                statement = ParseForEachStatement(); break;
            case (int)TokenType.FUNCTION:
                statement = ParseFunctionStatement(); break;
            case (int)TokenType.LOCAL:
                statement = ParseLocalStatement(); break;
            case (int)TokenType.RETURN:
                statement = ParseReturnStatement(); break;
            case (int)TokenType.BREAK:
                statement = ParseBreakStatement(); break;
            case (int)TokenType.CONTINUE:
                statement = ParseContinueStatement(); break;
            default:
                statement = ParseOtherStatement();
                break;
        }
        if (statement == null)
            break;
        block.statements.Add(statement);
    }
    return block;
}

특수한 곳, 마지막 두 개의stat, 값 부여 문장과 함수 호출 문장은 구분하기 어렵다.그들의 시작 구조는 유사한데 모두 Name {tableindex | funccall}, 함수 호출 문장의 끝은 funccall, 부치 문장은 아니다.즉, 접두사 구조를 비교해야 하지만 구조는 똑같으니 같은 함수로 해석하고 검사 결과 유형을 확인하면 된다.

bool IsVar(SyntaxTree t)
{
    return t is TableAccess || t is Terminator;
}

SyntaxTree ParseOtherStatement()
{
    // lua ， ，assign statement and func call
    SyntaxTree exp;
    if (LookAhead().m_type == (int)TokenType.NAME)
    {
        exp = ParsePrefixExp();
        if(IsVar(exp))
        {
            // assign statement
            var assign_statement = new AssignStatement();
            assign_statement.var_list.Add(exp);
            while(LookAhead().m_type != (int)'=')
            {
                if (NextToken().m_type != (int)',')
                    throw new ParserException("expect ',' to split var-list");
                if (LookAhead().m_type != (int)TokenType.NAME)
                    throw new ParserException("expect 'id' to start var");
                exp = ParsePrefixExp();
                if (!IsVar(exp))
                    throw new ParserException("expect var here");
                assign_statement.var_list.Add(exp);
            }
            NextToken();// skip '='
            assign_statement.exp_list = ParseExpList();
            return assign_statement;
        }
        else
        {
            Debug.Assert(exp is FuncCall);
            return exp;
        }
    }
    else
    {
        if (IsMainExp())
            throw new ParserException("incomplete statement");
        return null;
    }
}

산자 우선 분석법

위의 BNF는 귀속 하강 방법으로는 해석할 수 없는 부분이 있다. 문법 정의에 귀속 구조가 존재하고 기본적으로 모든 언어에 이런 표현식 문장이 있다.

exp ::= mainexp | exp binop exp

여기에 상당한 간소화를 하였는데 mainexp포함 "(" exp ")" | unop exp, 간소화 후 표현식은 가장 간단한 이원 표현식이다.이원 표현식은 가장 기본적인 표현식이다. 산자 우선 분석법은 이런 문법 구조를 잘 해석할 수 있다.텍스트 약술 과정: 두 개의 창고, 조작 수잔과 조작 부호 창고를 설정합니다.스캔 표현식, 조작 수가 직접 창고에 들어오고 조작 부호를 만났을 때 우선순위 판단을 하여 다음 조작을 확정합니다.만약 조작부호의 우선순위가 창고 꼭대기 조작부호보다 높으면 창고에 들어갑니다.그렇지 않으면 창고 상단 조작부호를 팝업하고 조작수 창고에서 두 개의 조작수를 팝업하여 이원 표현식으로 조합하여 새로운 조작수로 창고에 넣고 현재 조작부호가 창고에 들어갈 때까지 이 과정을 계속합니다.코드를 쓸 때 함수 호출 창고로 조작 창고와 조작 창고를 대체할 수 있는 특별한 기교가 있다.

        SyntaxTree ParseExp(int left_priority = 0)
        {
            var exp = ParseMainExp();
            while(true)
            {
                int right_priority = GetOpPriority(LookAhead());
                if (left_priority < right_priority ||(left_priority == right_priority && IsRightAssociation(LookAhead())))
                {
                    // C++ ， ， ， C++ 
                    var op = NextToken();
                    exp = new BinaryExpression(exp, op, ParseExp(right_priority));
                }
                else
                {
                    return exp;
                }
            }
        }