spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Quellcode

#
# ======= Expression Grammar Productions (3rd Approach) - 22/12/2013 =======
#

# Basics
Digit               ::= '0' | ... | '9'
Letter              ::= 'a' | ... | 'z' | 'A' | ... | 'Z'
Number              ::= Digit ( Digit )*
Identifier          ::= ( '_' | Letter ) ( '_' | Letter | Digit )*

# Literals
Literal             ::= IntLiteral
IntLiteral          ::= Number
FloatLiteral        ::= Number '.' Number
BoolLitearl         ::= 'true' | 'false'

# Object identifiers
ArrayIndex          ::= ArithmeticExpr
ObjectName          ::= Identifier ( '.' Identifier )*
Object              ::= ObjectName ( '[' ArrayIndex ']' )*

# Function arguments
ArgList             ::= epsilon | SingleArg ( ',' SingleArg )*
SingleArg           ::= BooleanExpr | ArithmeticExpr

# Sum expressions
ArithmeticExpr      ::= SumExpr
SumExpr             ::= ProductExpr ( ( '+' | '-' ) ProductExpr )*
ProductExpr         ::= ValueExpr ( ( '*' | '/' | '%' ) ValueExpr )*
ValueExpr           ::= Literal | MemoryObject | BracketExpr | CastExpr | CallExpr
BracketExpr         ::= '(' ArithmeticExpr ')'
CastExpr            ::= '(' TypeDenoter ')' ValueExpr
CallExpr            ::= ObjectName '(' ArgList ')'

# Bool expressions
BooleanExpr         ::= LinkedOrExpr
LinkedOrExpr        ::= LinkedAndExpr ( '||' LinkedAndExpr )*
LinkedAndExpr       ::= ValueBoolExpr ( '&&' ValueBoolExpr )*
ValueBoolExpr       ::= BoolLitearl | RelationExpr | NegBoolExpr
RelationExpr        ::= ArithmeticExpr ( '=' | '!=' | '<' | '>' | '<=' | '>=' ) ArithmeticExpr
NegBoolExpr         ::= '!' BooleanExpr

# Assignment statements
MemoryObject        ::= ObjectName | AssignStatement
AssignStatement     ::= LeftAssign | IncDecAssign
LeftAssign          ::= MemoryObject ( ':=' | '+=' | '-=' | '*=' | '/=' | '%=' | '|=' | '&=' | '^=' | '<<=' | '>>=' ) ( BooleanExpr | ArithmeticExpr )
IncDecAssign        ::= PreIncDecAssign | PostIncDecAssign
PreIncDecAssign     ::= ( '++' | '--' ) MemoryObject
PostIncDecAssign    ::= MemoryObject ( '++' | '--' )

# === Use case example (Pseudo Code) ===

# Example code (of my language):
#
#   if x + 2 > 3 - (2 + func(x - 2, true)) * y {
#       x := 2 + ++y - func(y, false)
#       i++
#   }
#

AcceptToken(Type) {
    if (CurrentTokenType == Type)
        GetNextToken()
    else
        Error()
}

ParseIfStatement() {
    AcceptToken('if')
    ParseBooleanExpression()
    ParseStatementBlock()
}

ParseStatementBlock() {
    AcceptToken('{')
    while (CurrentTokenType != '}') {
        ParseStatement()
    }
    AcceptToken('}')
}

Quellcode

int x
int x()

C-/C++-Quelltext

Program               ::= ( Command )*    // "Program" ist das Start-Symbol
CommandBlock          ::= '{' ( Command )* '}'
Command               ::= IfCommand | ClassDeclaration | CommandBlock | EnumerationDefinition
IfCommand             ::= 'if' BooleanExpression CommandBlock ( 'elif' BooleanExpression CommandBlock )* ( epsilon | 'else' CommandBlock )
ClassDeclaration      ::= 'class' Identifier ClassCommandBlock
ClassCommandBlock     ::= '{' ( ClassCommand )* '}'
ClassCommand          ::= ClassDeclaration | PrivacySpecifier | EnumerationDefinition
PrivacySpecifier      ::= 'public:' | 'private:' | 'protected:'
EnumerationDefinition ::= 'enum' Identifier EnumerationBlock
EnumerationBlock      ::= '{' ( Identifier )* '}'

Quellcode

# Basics
Digit                   ::= '0' | ... | '9'
Letter                  ::= 'a' | ... | 'z' | 'A' | ... | 'Z'
Number                  ::= Digit ( Digit )*
Identifier              ::= ( '_' | Letter ) ( '_' | Letter | Digit )*

# Literals
Literal                 ::= IntLiteral | FloatLiteral | BoolLiteral
IntLiteral              ::= Number
FloatLiteral            ::= Number '.' Number
BoolLitearl             ::= 'true' | 'false'
StringLiteral           ::= '"' ( AnyCharacter )* '"'
ArithmeticLiteral       ::= IntLiteral | FloatLiteral

# Object identifiers
ArrayIndex              ::= ArithmeticExpr
ObjectName              ::= Identifier ( '.' Identifier )*
Object                  ::= ObjectName ( '[' ArrayIndex ']' )*

# Arithmetic expressions
ArithmeticExpr          ::= BitwiseOrExpr
BitwiseOrExpr           ::= BitwiseXorExpr ( '|' BitwiseXorExpr )*
BitwiseXorExpr          ::= BitwiseAndExpr ( '^' BitwiseAndExpr )*
BitwiseAndExpr          ::= ShiftExpr ( '&' ShiftExpr )*
ShiftExpr               ::= SumExpr ( ( '<<' | '>>' ) SumExpr )*
SumExpr                 ::= ProductExpr ( ( '+' | '-' ) ProductExpr )*
ProductExpr             ::= ValueExpr ( ( '*' | '/' | '%' ) ValueExpr )*
ValueExpr               ::= ArithmeticLiteral | MemoryObject | ArithmeticBracketExpr | CastExpr | CallExpr
ArithmeticBracketExpr   ::= '(' ArithmeticExpr ')'
CastExpr                ::= '(' TypeDenoter ')' ValueExpr
CallExpr                ::= ObjectName '(' ArgList ')'

# Assignment statements
MemoryObject            ::= Object | AssignStatement
AssignStatement         ::= LeftAssign | IncDecAssign
LeftAssign              ::= MemoryObject ( ':=' | '+=' | '-=' | '*=' | '/=' | '%=' | '|=' | '&=' | '^=' | '<<=' | '>>=' ) ( BooleanExpr | ArithmeticExpr )
IncDecAssign            ::= PreIncDecAssign | PostIncDecAssign
PreIncDecAssign         ::= ( '++' | '--' ) MemoryObject
PostIncDecAssign        ::= MemoryObject ( '++' | '--' )

C-/C++-Quelltext

// ----- PSEUDOCODE for Expression Parsing -----

ParseArithmeticExpr()
{
    return ParseBitwiseOrExpr();
}

ParseBitwiseOrExpr()
{
    auto ExprAST = new BitwiseOrExpression;

    ExprAST->XorExprList.push_back(ParseBitwiseXorExpr());

    while (TokenType() == '|')
    {
        AcceptIt();
        ExprAST->XorExprList.push_back(ParseBitwiseXorExpr());
    }

    return ExprAST;
}

ParseBitwiseXorExpr()
{
    auto ExprAST = new BitwiseXorExpression;

    ExprAST->AndExprList.push_back(ParseBitwiseAndExpr());

    while (TokenType() == '^')
    {
        AcceptIt();
        ExprAST->AndExprList.push_back(ParseBitwiseAndExpr());
    }

    return ExprAST;
}

ParseBitwiseAndExpr()
{
    auto ExprAST = new BitwiseAndExpression;

    ExprAST->ShiftExprList.push_back(ParseShiftExpr());

    while (TokenType() == '&')
    {
        AcceptIt();
        ExprAST->ShiftExprList.push_back(ParseShiftExpr());
    }

    return ExprAST;
}

ParseShiftExpr()
{
    auto ExprAST = new ShiftExpression;

    ExprAST->SumExprList.push_back(ParseSumExpr());

    while (TokenType() == '<<' || TokenType() == '>>')
    {
        AcceptIt();
        ExprAST->SumExprList.push_back(ParseSumExpr());
    }

    return ExprAST;
}

ParseSumExpr()
{
    auto ExprAST = new SumExpression;

    ExprAST->ProductExprList.push_back(ParseProductExpr());

    while (TokenType() == '+' || TokenType() == '-')
    {
        AcceptIt();
        ExprAST->ProductExprList.push_back(ParseProductExpr());
    }

    return ExprAST;
}

ParseProductExpr()
{
    auto ExprAST = new ProductExpression;

    ExprAST->SumExprList.push_back(ParseValueExpr());

    while (TokenType() == '*' || TokenType() == '/' || TokenType() == '%')
    {
        AcceptIt();
        ExprAST->SumExprList.push_back(ParseValueExpr());
    }

    return ExprAST;
}

ParseValueExpr()
{
    auto ExprAST = new ValueExpression;

    switch (TokenType())
    {
        case IntLiteral:
        case FloatLiteral:
            return ParseArithmeticLiteral();

        case '(':
            return ParseArithmeticBracketExprOrCastExpr();
        
        case Identifer:
            return ParseMemoryObjectOrCallExpr();

        default:
            ErrorUnexpectedToken();
    }

    return ExprAST;
}

ParseArithmeticBracketExprOrCastExpr()
{
    // Store information where we are currently reading in file.
    Scanner_.PushPos();

    // Try to parse a cast expression ('false' means it is not required).
    auto CastExprAST = ParseCastExpr(false);

    if (CastExprAST == nullptr)
    {
        // Restore position we were reading before trying to find a cast expression.
        Scanner_.PopPosAndRestore();

        // Now try to parse bracket expression.
        return ParseArithmeticBracketExpr();
    }
    else
    {
        // Pop stored position from the scanner's stack and continue reading by ignoring the poped data.
        Scanner_.PopPosAndIgnore();

        return CastExprAST;
    }
}

ParseCastExpr(bool Required)
{
    if (TokenType() == '(')
        AcceptIt();
    else
    {
        if (Required)
            ErrorUnexpectedToken("Expected '('");
        return nullptr;
    }

    // Parse type denoter to which the value expression is to be casted.
    auto TypeDenoterAST = ParseTypeDenoter(Required);

    if (TypeDenoterAST == nullptr)
        return nullptr;

    if (TokenType() == ')')
        AcceptIt();
    else
    {
        if (Required)
            ErrorUnexpectedToken("Expected ')'");
        return nullptr;
    }

    // Parse the value expression which is to be casted.
    auto ValueExprAST = ParseValueExpr();

    auto CastExprAST = new CastExpression;

    CastExprAST->TypeDenoter    = TypeDenoterAST;
    CastExprAST->ValueExpr      = ValueExprAST;

    return CastExprAST;
}   

ParseArithmeticBracketExpr()
{
    auto ExprAST = new ArithmeticBracketExpr;

    Accept('(');
    {
        ExprAST->ArithmeticExpr = ParseArithmeticExpr();
    }
    Accept(')');

    return ExprAST;
}

ParseMemoryObjectOrCallExpr()
{
    // For memory object and call epxression we need an object-name AST node
    auto ObjectNameAST = ParseObjectName();

    if (TokenType() == '(')
    {
        // If the object name is followed by a '(' character it must be a function call.
        return ParseCallExpr(ObjectNameAST);
    }
    else
    {
        // Otherwise it must be an memory object
        return ParseMemoryObject(ObjectNameAST);
    }
}

ParseMemoryObject(ObjectName ObjectNameAST)
{
    // Check if object name has already been parsed; if not, do so.
    if (ObjectNameAST == nullptr)
        ObjectNameAST = ParseObjectName();

    auto MemObjectAST = new MemoryObject;
        
    MemObjectAST->ObjectName = ObjectNameAST;

    // Check for array indexing
    if (TokenType() == '[')
        MemObjectAST->ArrayIndexing = ParseArrayIndexing();

    // Check for assignment (:=, +=, -=, etc.)
    if (IsTokenAssignmentOperator())
        MemObjectAST->AssignStatement = ParseAssigStatement();

    return MemObjectAST;
}

ParseCallExpr(ObjectName ObjectNameAST)
{
    // Check if object name has already been parsed; if not, do so.
    if (ObjectNameAST == nullptr)
        ObjectNameAST = ParseObjectName();

    auto CallExprAST = new CallExpression;

    CallExprAST->FunctionName = ObjectNameAST;

    Accept('(');
    {
        CallExprAST->ArgList = ParseArgumentList();
    }
    Accept(')');

    return CallExprAST;
}

ParseObjectName()
{
    auto ObjectNameAST = new ObjectName;

    ObjectNameAST->IdentifierList.push_back(ParseIdentifier());

    // Parse further optional identifiers (separated by a '.' character).
    while (TokenType() == '.')
    {
        AcceptIt();
        ObjectNameAST->IdentifierList.push_back(ParseIdentifier());
    }

    return ObjectNameAST;
}

ParseIdentifier()
{
    auto IdentifierToken = Accept(Types::Identifier);
    return new Identifier(IdentifierToken);
}

ParseArithmeticLiteral()
{
    switch (TokenType())
    {
        case IntLiteral:
            auto CurrToken = AcceptIt();
            return new IntLiteral(CurrToken);
        case FloatLiteral:
            auto CurrToken = AcceptIt();
            return new FloatLiteral(CurrToken);
    }
    ErrorUnexpectedToken("Expected arithmetic literal")
}

Quellcode

int a := 7 + 3 * 2 - 5 * (6 + 3) - 4

Quellcode

; D:\SoftwareEntwicklung\C++\HLC\Tools\XieXie-Compiler\trunk\examples\Tests/ExpressionTest1.xx.asm
; XieXie generated source file
; Fri Dec 27 21:14:14 2013

; Variable initialization "a"
push 7
push 3
push 2
pop ebx
pop eax
mul eax, ebx
push eax
push 5
push 6
push 3
pop ebx
pop eax
add eax, ebx
push eax
pop ebx
pop eax
mul eax, ebx
push eax
pop ebx
pop eax
sub eax, ebx
push eax
push 4
pop ebx
pop eax
sub eax, ebx
push eax
pop ebx
pop eax
add eax, ebx
push eax

; ===============

Quellcode

push eax
pop eax