`
NeuronR
  • 浏览: 59023 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

[语法分析]LR语法分析器的构造

360F# 
阅读更多

    LR分析器的consumeNonTerminal函数在上一节提到过，其实跟Goto表没有关系：如果在分析器内部规约得到一个非终结符，那么规约函数执行结束之后，马上就会根据传入宏的“leftPart”在Goto表中查找对应的目标状态并压栈，而根本不用执行consumeNonTerminal函数。这个成员函数的用武之地在于接受其它分析器得到的非终结符，并在Goto表中“额外”的那一列里查找对应状态并压栈//

#define wrapname(name) name ## _LRAnalyser

static void wrapname(consumeNonTerminal)(void* self,
                                         struct AbstractSyntaxNode* nonTerminal)
{
    struct LRAnalyser* lra = (struct LRAnalyser*)self;
    struct LRState* currentState = (struct LRState*)
                                   (lra->stateStack->peek(lra->stateStack));
    lra->symbolStack->push(lra->symbolStack, nonTerminal);
    lra->stateStack->push(lra->stateStack,
                          currentState->gotoes[NR_GOTO_TABLE_COLUMN]);
}

    接下来是consumeToken函数，这个函数的职责是在SLR(1)分析预测表中寻找函数入口地址并进入。如果在表内对应的项目为NULL，那么就中断。中断的原因有这么几个：错误；当前LR分析器是个受委托的分析器，遇到外层反花括号；当前分析结束，已经转到状态LRState1（留心观察一下预测分析表的构造，状态LRState1对任何终结符都没有兴趣）。现在我们需要将正常状态和错误状态进行区分。首先，如果在中断时当前状态栈栈顶是状态LRState1，那么这时一个基本块已经被正确识别了；然后，如果当前栈顶的是状态LRState0，那么有一种情况也是正常的，那就是遇到的是一个反花括号，也就是说输入是 "{ }" 空的语句块，读入正花括号后委托进入一个新LR分析器，接着这个分析器马上就遇到了反括号，因此栈顶还是初始状态。除此之外，就是出现了错误情况。

static void wrapname(consumeToken)(void* self, struct Token* token)
{
    struct LRAnalyser* lra = (struct LRAnalyser*)self;
    struct LRState* lrState = (struct LRState*)
                              (lra->stateStack->peek(lra->stateStack));
    if(NULL != lrState->actions[token->type]) {
        lrState->actions[token->type](lra, token); // 正常action
    } else {
        struct AbstractSyntaxNode* ret;
        struct LRState* topState = (struct LRState*)(lra->stateStack->pop(lra->stateStack));
        if((jerryLRStates + LRState0 == topState && RBRACE == token->type)
           || jerryLRStates + LRState1 == topState) {
            ret = lra->symbolStack->pop(lra->symbolStack); // 如果是空语句块，那么得到的是 NULL
            // 清理当前分析器
            struct SyntaxAnalyser* analyser = (struct SyntaxAnalyser*)
                                             (analyserStack->peek(analyserStack));
            analyser->consumeNonTerminal(analyser, ret);
            analyser = (struct SyntaxAnalyser*)
                       (analyserStack->peek(analyserStack));
            analyser->consumeToken(analyser, token);
        } else {
            // 出错
        }
    }
}

    在没有错误的情况下清理分析器是一件简单的事情，因为此时符号栈应该已经空了，所以只需要调用栈的析构函数，而不需关心非终结符。

static void wrapname(cleanup)(struct LRAnalyser* self)
{
    struct AbstractSyntaxNode* node;
    self->symbolStack->finalize(self->symbolStack);
    revert(self->symbolStack);
    self->stateStack->finalize(self->stateStack);
    revert(self->stateStack);

    analyserStack->pop(analyserStack); // 弹出自己
    revert(self);
}

    最后就是分析器的构造函数了。

struct SyntaxAnalyser* newLRAnalyser(void)
{
    struct LRAnalyser* analyser = (struct LRAnalyser*)
                                          allocate(sizeof(struct LRAnalyser));

    analyser->symbolStack = newStack();
    analyser->stateStack = newStack();
    analyser->stateStack->push(analyser->stateStack, jerryLRStates);

    analyser->consumeToken = wrapname(consumeToken);
    analyser->consumeNonTerminal = wrapname(consumeNonTerminal);

    return (struct SyntaxAnalyser*)analyser;
}

在构造时，会向状态栈中压入初始状态jerryLRStates( + 0)，也就是状态LRState0。这样一个LR分析器就完成了。

附：LR分析器及预测分析表不含错误处理部分的代码

    错误处理会在某个时候集中进行。

 

#include<stdlib.h>
#include"datastruct.h"
#include"syntax-analyser.h"
#include"syntax-node.h"

#include"COOL/MemoryAllocationDebugger.h"
#include"COOL/Stack/Stack.h"

extern struct Stack* analyserStack;
extern struct SyntaxAnalyser* newVariableAnalyser(void);
extern struct SyntaxAnalyser* newOperationAnalyser(void);

static struct LRState* jerryLRStates = NULL;

#define linkName(f, l) f ## _m_ ## l

#define popStateStack(stack, nr) (stack)->pops(stack, nr, NULL)
static void linkName(BasicBlock, Null)(struct LRAnalyser* analyser)
{
    analyser->symbolStack->push(analyser->symbolStack, NULL);
}

static void linkName(BasicBlock, SentenceBasicBlock)
                                 (struct LRAnalyser* analyser)
{
    struct AbstractSyntaxNode* block = (struct AbstractSyntaxNode*)
                            (analyser->symbolStack->pop(analyser->symbolStack));
    struct AbstractSyntaxNode* sentence = (struct AbstractSyntaxNode*)
                            (analyser->symbolStack->pop(analyser->symbolStack));
    if(NULL != sentence) {
        sentence->nextNode = block;
        block = sentence;
    }
    analyser->symbolStack->push(analyser->symbolStack, block);
    popStateStack(analyser->stateStack, 2);
}

static void linkName(Sentence, EoS)(struct LRAnalyser* analyser)
{
    analyser->symbolStack->push(analyser->symbolStack, NULL);
    popStateStack(analyser->stateStack, 1);
}

static void linkName(Sentence, IfElseBranch)(struct LRAnalyser* analyser)
{
    struct AbstractSyntaxNode* invalidSuit = (struct AbstractSyntaxNode*)
                            (analyser->symbolStack->pop(analyser->symbolStack));
    struct AbstractSyntaxNode* validSuit = (struct AbstractSyntaxNode*)
                            (analyser->symbolStack->pop(analyser->symbolStack));
    struct AbstractValueNode* condition = (struct AbstractValueNode*)
                            (analyser->symbolStack->pop(analyser->symbolStack));
    analyser->symbolStack->push(analyser->symbolStack,
                              newIfElseNode(condition, validSuit, invalidSuit));
    popStateStack(analyser->stateStack, 6);
}

static void linkName(Sentence, WhileLoop)(struct LRAnalyser* analyser)
{
    struct AbstractSyntaxNode* loop = (struct AbstractSyntaxNode*)
                            (analyser->symbolStack->pop(analyser->symbolStack));
    struct AbstractValueNode* condition = (struct AbstractValueNode*)
                            (analyser->symbolStack->pop(analyser->symbolStack));
    analyser->symbolStack->push(analyser->symbolStack,
                                newWhileNode(condition, loop));
    popStateStack(analyser->stateStack, 5);
}

static void linkName(Sentence, TypeVariableRegisterEoS)
                               (struct LRAnalyser* analyser)
{
    popStateStack(analyser->stateStack, 3);
}

static void linkName(Sentence, IOAssignmentEoS)(struct LRAnalyser* analyser)
{
    struct AbstractValueNode* expression = (struct AbstractValueNode*)
                            (analyser->symbolStack->pop(analyser->symbolStack));
    struct IONode* node = (struct IONode*)(analyser->symbolStack->
                                           peek(analyser->symbolStack));
    node->expression = expression;
    popStateStack(analyser->stateStack, 3);
}

static void linkName(Sentence, AssignmentEoS)(struct LRAnalyser* analyser)
{
    struct AbstractValueNode* arith = (struct AbstractValueNode*)
                            (analyser->symbolStack->pop(analyser->symbolStack));
    analyser->symbolStack->push(analyser->symbolStack,
                                newArithmaticNode(arith));
    popStateStack(analyser->stateStack, 2);
}

static void linkName(Sentence, BreakEoS)(struct LRAnalyser* analyser)
{
    analyser->symbolStack->push(analyser->symbolStack, newBreakNode());
    popStateStack(analyser->stateStack, 2);
}

static void linkName(ElseBlock, Null)(struct LRAnalyser* analyser)
{
    analyser->symbolStack->push(analyser->symbolStack, NULL);
}

static void linkName(ElseBlock, ElseBasicBlock)(struct LRAnalyser* analyser)
{
    popStateStack(analyser->stateStack, 2);
}

static void linkName(Initialization, Null)(struct LRAnalyser* analyser)
{
    analyser->symbolStack->push(analyser->symbolStack, NULL);
}

static void linkName(Sentence, LBraceBasicBlockRBrace)
                               (struct LRAnalyser* analyser)
{
    struct AbstractSyntaxNode* innerBlock = (struct AbstractSyntaxNode*)
                            (analyser->symbolStack->pop(analyser->symbolStack));
    analyser->symbolStack->push(analyser->symbolStack,
                                newBasicBlockNode(innerBlock));
    popStateStack(analyser->stateStack, 3);
}

static void linkName(Initialization, AssignAssignment)
                               (struct LRAnalyser* analyser)
{
    popStateStack(analyser->stateStack, 2);
}

static void linkName(VariableRegister, VariableInitialization)
                                       (struct LRAnalyser* analyser)
{
    void* initialValue = analyser->symbolStack->pop(analyser->symbolStack);
    void* variable = analyser->symbolStack->pop(analyser->symbolStack);

    struct DeclarationNode* decl = (struct DeclarationNode*)
                                       (analyser->symbolStack->
                                                 peek(analyser->symbolStack));
    decl->vars->enqueue(decl->vars, variable);
    decl->initVals->enqueue(decl->initVals, initialValue);
    popStateStack(analyser->stateStack, 2);
}

#define shift(current, encounter, target)                                 \
    static void linkName(current, encounter)(struct LRAnalyser* self,     \
                                             struct Token* t)             \
    {                                                                     \
        self->stateStack->push(self->stateStack, jerryLRStates + target); \
    } /*******************************************************************/
shift(Sentence_AssignmentEoS_1, EOS, Sentence_AssignmentEoS_2)
shift(Sentence_BreakEoS_1, EOS, Sentence_BreakEoS_2)
shift(Sentence_LBraceBasicBlockRBrace_2, RBRACE,
      Sentence_LBraceBasicBlockRBrace_3)
shift(IfElseBranch_1, LPARENT, IfElseBranch_2)
shift(IfElseBranch_3, RPARENT, IfElseBranch_4)
shift(IfElseBranch_5, ELSE, ElseBlock_1)
shift(WhileLoop_1, LPARENT, WhileLoop_2)
shift(WhileLoop_3, RPARENT, WhileLoop_4)
shift(VariableRegister_VariableInitialization_1, ASSIGN,
      Initialization_AssignAssignment_1)
shift(DeclarationVariableRegister, EOS, Declaration_3)
shift(Sentence_IOAssignmentEoS_2, EOS, Sentence_IOAssignmentEoS_3)
#define shiftFirstSentence(current)                                         \
    shift(current, EOS,    Sentence_EoS_1)                                  \
    shift(current, LBRACE, Sentence_LBraceBasicBlockRBrace_1)               \
    shift(current, IF,     IfElseBranch_1)                                  \
    shift(current, WHILE,  WhileLoop_1)                                     \
    shift(current, BREAK,  Sentence_BreakEoS_1)                             \
    static void linkName(current, INTEGER_TYPE)(struct LRAnalyser* self,    \
                                                 struct Token* t)           \
    {                                                                       \
        self->symbolStack->push(self->symbolStack,                          \
                                newDeclarationNode(t->type));               \
        self->stateStack->push(self->stateStack,                            \
                               jerryLRStates + Declaration_1);              \
    }                                                                       \
                                                                            \
    static void linkName(current, REAL_TYPE)(struct LRAnalyser* self,       \
                                              struct Token* t)              \
    {                                                                       \
        self->symbolStack->push(self->symbolStack,                          \
                                newDeclarationNode(t->type));               \
        self->stateStack->push(self->stateStack,                            \
                               jerryLRStates + Declaration_1);              \
    }                                                                       \
                                                                            \
    static void linkName(current, READ)(struct LRAnalyser* self,            \
                                        struct Token* t)                    \
    {                                                                       \
        self->symbolStack->push(self->symbolStack, newIONode(t->type));     \
        self->stateStack->push(self->stateStack,                            \
                               jerryLRStates + Sentence_IOAssignmentEoS_1); \
    }                                                                       \
                                                                            \
    static void linkName(current, WRITE)(struct LRAnalyser* self,           \
                                         struct Token* t)                   \
    {                                                                       \
        self->symbolStack->push(self->symbolStack, newIONode(t->type));     \
        self->stateStack->push(self->stateStack,                            \
                               jerryLRStates + Sentence_IOAssignmentEoS_1); \
    } /*********************************************************************/
shiftFirstSentence(LRState0)
shiftFirstSentence(BasicBlock_SentenceBasicBlock_1)
shiftFirstSentence(IfElseBranch_4)
shiftFirstSentence(WhileLoop_4)
shiftFirstSentence(ElseBlock_1)
#undef shiftFirstSentence
#undef shift

static void linkName(DeclarationVariableRegister, COMMA)
                                      (struct LRAnalyser* self, struct Token* t)
{
    popStateStack(self->stateStack, 1);
}

#undef popStateStack

#define switchAnalyser(current, encounter, analyser)                  \
    static void linkName(current, encounter)(struct LRAnalyser* self, \
                                             struct Token* t)         \
    {                                                                 \
        struct SyntaxAnalyser* delegateAnalyser = (analyser);         \
        analyserStack->push(analyserStack, delegateAnalyser);         \
        delegateAnalyser->consumeToken(delegateAnalyser, t);          \
    } /***************************************************************/
switchAnalyser(Declaration_1, IDENT,  newVariableAnalyser())
#define switchAnalyserFirstAssignment(current, analyser) \
    switchAnalyser(current, PLUS,    analyser)           \
    switchAnalyser(current, MINUS,   analyser)           \
    switchAnalyser(current, NOT,     analyser)           \
    switchAnalyser(current, INTEGER, analyser)           \
    switchAnalyser(current, REAL,    analyser)           \
    switchAnalyser(current, IDENT,   analyser)           \
    switchAnalyser(current, LPARENT, analyser) /*********/
switchAnalyserFirstAssignment(LRState0,       newOperationAnalyser())
switchAnalyserFirstAssignment(IfElseBranch_2, newOperationAnalyser())
switchAnalyserFirstAssignment(WhileLoop_2,    newOperationAnalyser())
switchAnalyserFirstAssignment(IfElseBranch_4, newOperationAnalyser())
switchAnalyserFirstAssignment(WhileLoop_4,    newOperationAnalyser())
switchAnalyserFirstAssignment(ElseBlock_1,    newOperationAnalyser())
switchAnalyserFirstAssignment(Sentence_IOAssignmentEoS_1,
                              newOperationAnalyser())
switchAnalyserFirstAssignment(BasicBlock_SentenceBasicBlock_1,
                              newOperationAnalyser())
switchAnalyserFirstAssignment(Initialization_AssignAssignment_1,
                              newOperationAnalyser())
#define switchAnalyserFirstSentence(current, analyser) \
    switchAnalyser(current, IF,           analyser)    \
    switchAnalyser(current, WHILE,        analyser)    \
    switchAnalyser(current, READ,         analyser)    \
    switchAnalyser(current, WRITE,        analyser)    \
    switchAnalyser(current, BREAK,        analyser)    \
    switchAnalyser(current, INTEGER_TYPE, analyser)    \
    switchAnalyser(current, REAL_TYPE,    analyser)    \
    switchAnalyser(current, EOS,          analyser)    \
    switchAnalyser(current, LBRACE,       analyser)    \
    switchAnalyserFirstAssignment(current, analyser) ///
switchAnalyserFirstSentence(Sentence_LBraceBasicBlockRBrace_1, newLRAnalyser())
switchAnalyser(Sentence_LBraceBasicBlockRBrace_1, RBRACE, newLRAnalyser())
#undef switchAnalyserFirstSentence
#undef switchAnalyserFirstAssignment
#undef switchAnalyser

#define reduce(current, encounter, leftPart, rightPart)                    \
static void linkName(current, encounter)(struct LRAnalyser* self,          \
                                         struct Token* t)                  \
{                                                                          \
    linkName(leftPart, rightPart)(self);                                   \
    struct LRState* target = ((struct LRState*)self->stateStack->          \
                                peek(self->stateStack))->gotoes[leftPart]; \
    self->stateStack->push(self->stateStack, target);                      \
    self->consumeToken(self, t);                                           \
} /************************************************************************/
reduce(LRState0, END,    BasicBlock, Null)
reduce(LRState0, RBRACE, BasicBlock, Null)
reduce(LRState0, ELSE,   BasicBlock, Null)

reduce(BasicBlock_SentenceBasicBlock_1, END,    BasicBlock, Null)
reduce(BasicBlock_SentenceBasicBlock_1, RBRACE, BasicBlock, Null)
reduce(BasicBlock_SentenceBasicBlock_1, ELSE,   BasicBlock, Null)

reduce(VariableRegister_VariableInitialization_1, EOS,   Initialization, Null)
reduce(VariableRegister_VariableInitialization_1, COMMA, Initialization, Null)

reduce(IfElseBranch_5, RBRACE, ElseBlock, Null)
reduce(IfElseBranch_5, END,    ElseBlock, Null)
#define reduceFirstSentence(current, leftPart, rightPart) \
    reduce(current, IF,           leftPart, rightPart)    \
    reduce(current, WHILE,        leftPart, rightPart)    \
    reduce(current, READ,         leftPart, rightPart)    \
    reduce(current, WRITE,        leftPart, rightPart)    \
    reduce(current, BREAK,        leftPart, rightPart)    \
    reduce(current, INTEGER_TYPE, leftPart, rightPart)    \
    reduce(current, REAL_TYPE,    leftPart, rightPart)    \
    reduce(current, INTEGER,      leftPart, rightPart)    \
    reduce(current, REAL,         leftPart, rightPart)    \
    reduce(current, NOT,          leftPart, rightPart)    \
    reduce(current, PLUS,         leftPart, rightPart)    \
    reduce(current, MINUS,        leftPart, rightPart)    \
    reduce(current, IDENT,        leftPart, rightPart)    \
    reduce(current, EOS,          leftPart, rightPart)    \
    reduce(current, LBRACE,       leftPart, rightPart)    \
    reduce(current, LPARENT,      leftPart, rightPart) /**/
reduceFirstSentence(IfElseBranch_5, ElseBlock, Null)
#define reduceAny(current, leftPart, rightPart)        \
    reduceFirstSentence(current, leftPart, rightPart)  \
    reduce(current, END,          leftPart, rightPart) \
    reduce(current, ELSE,         leftPart, rightPart) \
    reduce(current, MULTIPLY,     leftPart, rightPart) \
    reduce(current, DIVIDE,       leftPart, rightPart) \
    reduce(current, ASSIGN,       leftPart, rightPart) \
    reduce(current, LT,           leftPart, rightPart) \
    reduce(current, LE,           leftPart, rightPart) \
    reduce(current, EQ,           leftPart, rightPart) \
    reduce(current, GT,           leftPart, rightPart) \
    reduce(current, GE,           leftPart, rightPart) \
    reduce(current, NE,           leftPart, rightPart) \
    reduce(current, AND,          leftPart, rightPart) \
    reduce(current, OR,           leftPart, rightPart) \
    reduce(current, COMMA,        leftPart, rightPart) \
    reduce(current, RPARENT,      leftPart, rightPart) \
    reduce(current, LBRACKET,     leftPart, rightPart) \
    reduce(current, RBRACKET,     leftPart, rightPart) \
    reduce(current, RBRACE,       leftPart, rightPart)
reduceAny(Sentence_EoS_1, Sentence, EoS)
reduceAny(BasicBlock_SentenceBasicBlock_2, BasicBlock, SentenceBasicBlock)
reduceAny(Sentence_IOAssignmentEoS_3, Sentence, IOAssignmentEoS)
reduceAny(IfElseBranch_6, Sentence, IfElseBranch)
reduceAny(ElseBlock_2, ElseBlock, ElseBasicBlock)
reduceAny(WhileLoop_5, Sentence, WhileLoop)
reduceAny(Sentence_AssignmentEoS_2, Sentence, AssignmentEoS)
reduceAny(Sentence_BreakEoS_2, Sentence, BreakEoS)
reduceAny(Declaration_3, Sentence, TypeVariableRegisterEoS)
reduceAny(Sentence_LBraceBasicBlockRBrace_3, Sentence, LBraceBasicBlockRBrace)
reduceAny(Initialization_AssignAssignment_2, Initialization, AssignAssignment)
reduceAny(VariableRegister_VariableInitialization_2, VariableRegister,
          VariableInitialization)
#undef reduceAny
#undef reduce

void initialLRStates(void)
{
    jerryLRStates = (struct LRState*)
                            allocate(NR_LR_STATE * sizeof(struct LRState));
    memset(jerryLRStates, 0, NR_LR_STATE * sizeof(struct LRState));
#define setAction(state, encounter)                                    \
        jerryLRStates[state].actions[encounter] = linkName(state, encounter)
    setAction(LRState0, END);
    setAction(LRState0, RBRACE);
    setAction(LRState0, ELSE);
    setAction(BasicBlock_SentenceBasicBlock_1, END);
    setAction(BasicBlock_SentenceBasicBlock_1, RBRACE);
    setAction(BasicBlock_SentenceBasicBlock_1, ELSE);
    setAction(Sentence_AssignmentEoS_1, EOS);
    setAction(Sentence_BreakEoS_1, EOS);
    setAction(Sentence_LBraceBasicBlockRBrace_2, RBRACE);
    setAction(IfElseBranch_1, LPARENT);
    setAction(IfElseBranch_3, RPARENT);
    setAction(IfElseBranch_5, ELSE);
    setAction(IfElseBranch_5, RBRACE);
    setAction(IfElseBranch_5, END);
    setAction(WhileLoop_1, LPARENT);
    setAction(WhileLoop_3, RPARENT);
    setAction(VariableRegister_VariableInitialization_1, ASSIGN);
    setAction(DeclarationVariableRegister, EOS);
    setAction(DeclarationVariableRegister, COMMA);
    setAction(Sentence_IOAssignmentEoS_2, EOS);
    setAction(VariableRegister_VariableInitialization_1, EOS);
    setAction(VariableRegister_VariableInitialization_1, COMMA);
    setAction(Declaration_1, IDENT);
    #define setActionFirstAssignment(state) \
        setAction(state, PLUS);             \
        setAction(state, MINUS);            \
        setAction(state, NOT);              \
        setAction(state, INTEGER);          \
        setAction(state, REAL);             \
        setAction(state, IDENT);            \
        setAction(state, LPARENT) /*********/
    setActionFirstAssignment(IfElseBranch_2);
    setActionFirstAssignment(WhileLoop_2);
    setActionFirstAssignment(Sentence_IOAssignmentEoS_1);
    setActionFirstAssignment(Initialization_AssignAssignment_1);
    #define setActionFirstSentence(state) \
        setAction(state, EOS);            \
        setAction(state, READ);           \
        setAction(state, WRITE);          \
        setAction(state, IF);             \
        setAction(state, WHILE);          \
        setAction(state, BREAK);          \
        setAction(state, INTEGER_TYPE);   \
        setAction(state, REAL_TYPE);      \
        setAction(state, LBRACE);         \
        setActionFirstAssignment(state) ///
    setActionFirstSentence(LRState0);
    setActionFirstSentence(BasicBlock_SentenceBasicBlock_1);
    setActionFirstSentence(IfElseBranch_4);
    setActionFirstSentence(IfElseBranch_5);
    setActionFirstSentence(WhileLoop_4);
    setActionFirstSentence(ElseBlock_1);
    setActionFirstSentence(Sentence_LBraceBasicBlockRBrace_1);
    setAction(Sentence_LBraceBasicBlockRBrace_1, RBRACE);
    #define setActionAny(state)         \
        setAction(state, END);          \
        setAction(state, ELSE);         \
        setAction(state, MULTIPLY);     \
        setAction(state, DIVIDE);       \
        setAction(state, ASSIGN);       \
        setAction(state, LT);           \
        setAction(state, LE);           \
        setAction(state, EQ);           \
        setAction(state, GT);           \
        setAction(state, GE);           \
        setAction(state, NE);           \
        setAction(state, AND);          \
        setAction(state, OR);           \
        setAction(state, COMMA);        \
        setAction(state, RPARENT);      \
        setAction(state, LBRACKET);     \
        setAction(state, RBRACKET);     \
        setAction(state, RBRACE);       \
        setActionFirstSentence(state) ///
    setActionAny(Sentence_EoS_1);
    setActionAny(BasicBlock_SentenceBasicBlock_2);
    setActionAny(Sentence_IOAssignmentEoS_3);
    setActionAny(IfElseBranch_6);
    setActionAny(ElseBlock_2);
    setActionAny(WhileLoop_5);
    setActionAny(Sentence_AssignmentEoS_2);
    setActionAny(Sentence_BreakEoS_2);
    setActionAny(Sentence_LBraceBasicBlockRBrace_3);
    setActionAny(Initialization_AssignAssignment_2);
    setActionAny(VariableRegister_VariableInitialization_2);
    setActionAny(Declaration_3);
    #undef setActionFirstAssignment
    #undef setActionFirstSentence
    #undef setActionAny
    #undef setAction

    #define setGoto(state, nonTerminal, target)                         \
        jerryLRStates[state].gotoes[nonTerminal] = jerryLRStates + target
    setGoto(LRState0, BasicBlock, LRState1);
    setGoto(LRState0, Sentence, BasicBlock_SentenceBasicBlock_1);
    setGoto(BasicBlock_SentenceBasicBlock_1, Sentence,
            BasicBlock_SentenceBasicBlock_1);
    setGoto(BasicBlock_SentenceBasicBlock_1, BasicBlock,
            BasicBlock_SentenceBasicBlock_2);
    setGoto(WhileLoop_4, Sentence, WhileLoop_5);
    setGoto(IfElseBranch_4, Sentence, IfElseBranch_5);
    setGoto(IfElseBranch_5, ElseBlock, IfElseBranch_6);
    setGoto(ElseBlock_1, Sentence, ElseBlock_2);
    setGoto(VariableRegister_VariableInitialization_1, Initialization,
            VariableRegister_VariableInitialization_2);
    setGoto(Declaration_1, VariableRegister, DeclarationVariableRegister);
    #undef setGoto

    #define extraGoto(source, target)                                         \
    jerryLRStates[source].gotoes[NR_GOTO_TABLE_COLUMN] = jerryLRStates + target
    extraGoto(LRState0,                        Sentence_AssignmentEoS_1);
    extraGoto(IfElseBranch_4,                  Sentence_AssignmentEoS_1);
    extraGoto(ElseBlock_1,                     Sentence_AssignmentEoS_1);
    extraGoto(WhileLoop_4,                     Sentence_AssignmentEoS_1);
    extraGoto(BasicBlock_SentenceBasicBlock_1, Sentence_AssignmentEoS_1);

    extraGoto(Sentence_LBraceBasicBlockRBrace_1,
              Sentence_LBraceBasicBlockRBrace_2);
    extraGoto(IfElseBranch_2, IfElseBranch_3);
    extraGoto(WhileLoop_2, WhileLoop_3);
    extraGoto(Sentence_IOAssignmentEoS_1, Sentence_IOAssignmentEoS_2);
    extraGoto(Initialization_AssignAssignment_1,
              Initialization_AssignAssignment_2);
    extraGoto(Declaration_1, VariableRegister_VariableInitialization_1);
    #undef extraGoto
}

#undef linkName

void destructLRStates(void)
{
    revert(jerryLRStates);
    jerryLRStates = NULL;
}

#define wrapname(name) name ## _LRAnalyser
static void wrapname(cleanup)(struct LRAnalyser* self)
{
    struct AbstractSyntaxNode* node;
    self->symbolStack->finalize(self->symbolStack);
    self->stateStack->finalize(self->stateStack);

    analyserStack->pop(analyserStack);
    revert(self);
}

static void wrapname(consumeToken)(void* self, struct Token* token)
{
    struct LRAnalyser* lra = (struct LRAnalyser*)self;
    struct LRState* lrState = (struct LRState*)
                              (lra->stateStack->peek(lra->stateStack));
    if(NULL != lrState->actions[token->type]) {
        lrState->actions[token->type](lra, token);
    } else {
//        printf("Interrupt LR\n");
        struct AbstractSyntaxNode* ret;
        struct LRState* topState = (struct LRState*)
                                        (lra->stateStack->pop(lra->stateStack));
        if((jerryLRStates + LRState0 == topState && RBRACE == token->type)
           || jerryLRStates + LRState1 == topState) {
            ret = lra->symbolStack->pop(lra->symbolStack);
            wrapname(cleanup)(lra);
//        printf("Cleaned...\n");
            struct SyntaxAnalyser* analyser = (struct SyntaxAnalyser*)
                                           (analyserStack->peek(analyserStack));
            analyser->consumeNonTerminal(analyser, ret);
            analyser = (struct SyntaxAnalyser*)
                       (analyserStack->peek(analyserStack));
            analyser->consumeToken(analyser, token);
        } else {
            printf("LR ERR\n");
            printf("%s\n", token->image);
            exit(0);
        }
    }
}

static void wrapname(consumeNonTerminal)(void* self,
                                         struct AbstractSyntaxNode* nonTerminal)
{
    struct LRAnalyser* lra = (struct LRAnalyser*)self;
    struct LRState* currentState = (struct LRState*)
                                   (lra->stateStack->peek(lra->stateStack));
    lra->symbolStack->push(lra->symbolStack, nonTerminal);
    lra->stateStack->push(lra->stateStack,
                          currentState->gotoes[NR_GOTO_TABLE_COLUMN]);
}

struct SyntaxAnalyser* newLRAnalyser(void)
{
    struct LRAnalyser* analyser = (struct LRAnalyser*)
                                          allocate(sizeof(struct LRAnalyser));

    analyser->symbolStack = newStack();
    analyser->stateStack = newStack();
    analyser->stateStack->push(analyser->stateStack, jerryLRStates);

    analyser->consumeToken = wrapname(consumeToken);
    analyser->consumeNonTerminal = wrapname(consumeNonTerminal);

    return (struct SyntaxAnalyser*)analyser;
}
#undef wrapname

 

 

分享到：
| [语法分析]LR分析器与其它分析器的交互
评论
3 楼 lwwin 2009-03-09  
哦，我把reduce写成action了>o<～
2 楼 NeuronR 2009-03-07  
lwwin 写道

嗯，编译没通过，shift的移除了，这个也去掉吧～

360.&nbsp;&nbsp;&nbsp; setAction(IfElseBranch_5, RBRACE);

我真会挑刺(-3-～


setAction(IfElseBranch_5, RBRACE);

这个不是根据shift来的，而是根据reduce来的。对应的那句宏函数在285行
reduce(IfElseBranch_5, RBRACE, ElseBlock, Null)

不知道你是不是弄掉了这个。

PS: 谢谢挑刺。
1 楼 lwwin 2009-03-07  
嗯，编译没通过，shift的移除了，这个也去掉吧～

360.    setAction(IfElseBranch_5, RBRACE);

我真会挑刺(-3-～
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    紫霞人上语法分析LR（1）分析器

    编译原理语法分析，C语言，自下而上分析法

    lR语法分析器设计.pdf

    LR语法分析器是一种用于解析上下文无关文法的高效工具，广泛应用于编译器设计中。LR分析器从左向右扫描输入字符串，并自底向上地进行语法分析，旨在判断输入字符串是否符合文法的语句。以下是关于LR分析器设计的一些...

    java编写的LR语法分析器（编译原理实验）

    java编写的LR语法分析器（编译原理实验） 本实验是基于java语言实现的LR语法分析器，旨在演示编译原理中的LR语法分析技术。LR语法分析器是编译原理中的一种重要技术，用于分析和识别源代码中的语法结构。 LR语法...

    用c++实现LR语法分析器

    通过LR分析表及三个栈形成对输入表达式的判断！ 。

    LR语法分析器 编译原理课程设计 源码

    本项目是基于LR语法分析器的课程设计源码，旨在帮助学习者深入理解和实践编译器构造的核心概念。 LR语法分析器的全称是“左到右扫描，右部优先”的语法分析器，其工作原理是自左向右读取输入符号串，并通过一套状态...

    编译原理课程设计-LR(1)语法分析模拟构造器的设计

    关键词：LR分析器，语法分析器，编译原理，文法判定 综上所述，LR(k)分析法是编译器设计中的关键部分，尤其是LR(1)分析器，它通过增加预测信息，有效地解决了LR(0)分析器可能出现的冲突问题，提高了语法分析的精确...

    LR1语法分析生成器

    在描述中提到的"加上框架代码，构造出LR1语法分析程序"，意味着LR1生成器不仅生成状态转换表，还会提供一些基础的框架代码，这些代码可以与状态转换表结合，用于构建完整的LR1解析器。框架代码通常包括输入符号的...

    编译原理上机源代码LR语法分析器

    《编译原理上机源代码LR语法分析器》 编译原理是计算机科学中的核心领域，涉及语言处理、解析技术等方面。LR语法分析是编译器设计中的一个重要环节，用于将高级语言转换为机器可执行的指令。这篇实验报告详细介绍了...

    LR(0)语法分析器程序

    LR(0)语法分析器是一种在编译原理中常见的解析技术，主要应用于处理上下文无关文法。这个程序是用C语言编写的，因此具备高度的可移植性和效率。 LR(0)分析器的核心思想是基于状态转移表，通过自底向上的方式逐层解析...

    语法分析器LR（0）

    总的来说，这个Java编写的LR(0)语法分析器提供了一个实践编译原理中LR分析方法的实例，对于学习编译器构造和理解LR解析算法具有很高的价值。通过阅读和研究这些类的源代码，我们可以更深入地了解LR(0)分析器的工作...

    LR0语法分析程序生成器

    LR0分析器是一种自底向上的语法分析方法，"LR"代表“Left-to-Right扫描输入，Rightmost derivation推导”，"0"表示它使用的是最简单的项集构造算法。它通过构建一个有限状态机来识别语言，这个状态机被称为分析表。...

    编译原理实验LR语法分析器

    本实验重点聚焦于语法分析阶段，特别是LR语法分析器的实现。LR分析器是一种自底向上的解析技术，常用于编译器设计，用于将源代码解析成抽象语法树（AST），从而进行后续的编译或解释工作。 LR语法分析器的全称是...

    LR（1）语法分析器

    LR(1)语法分析器是一种在编译原理中广泛使用的解析技术，主要用于处理上下文无关文法。这种分析器能够处理更复杂的语言结构，而不仅仅是简单的左递归或右递归表达式。以下是对LR(1)语法分析器及其相关知识点的详细...

    C++实现LR(1)语法分析器

    学校老师布置的作业，编译原理实验LR(1)语法分析器，使用C++语言，已经通过VS2019调试通过，欢迎大家下载！

    LR（0）语法分析器

    LR(0)语法分析器是一种基于上下文无关文法（Context-Free Grammar, CFG）的自动分析工具，广泛应用于编译器设计中。它通过构造一个LR(0)解析表，根据输入符号序列来决定如何进行分析，从而确定该序列是否符合文法...

    LR(0)语法分析器的实现代码（python） - 简书1

    LR(0)语法分析器是一种用于解析符合特定类型的上下文无关文法的工具。它基于LR分析方法，其中"LR"代表“从左到右扫描输入，从右most衍生树构造”。"0"表示分析器不使用任何前瞻信息。在本文中，我们将讨论如何使用...

    LR1语法分析器 java版本 含报告

    在使用此Java版本的LR1语法分析器之前，建议读者熟悉编译器的基本概念，特别是有关词法分析、语法分析和解析表构造的部分。 LR1分析器的核心思想是自底向上地构建一个解析树，通过对输入符号串进行一系列的 shift-...

    编译原理 语法分析器--LR（1）分析法

    根据题目提供的代码片段，我们可以看到这是一个基于LR(1)分析法的语法分析器实现。下面对代码进行详细解读： 1. **预处理指令定义**: - `#define SIZE 20`: 定义了栈的大小为20。 - `#define sSIZE 12`: 定义了...

    编译原理 lr语法分析器

    LR语法分析器是编译器设计中的一种重要工具，用于解析程序源代码，将其转化为中间形式，以便后续的编译阶段进行处理。本实验报告将深入探讨LR(0)语法分析器的工作原理及其应用。 LR分析，全称为“Left-to-Right，...

Magicbox
Global site tag (gtag.js) - Google Analytics