باستخدام Bison لتحليل قائمة العناصر

Question

أنا أكتب مترجم لمحرك التظليل وكل غرامة عمل حتى وصلت إلى جزء تحليل البيانات.

لقد استخدمت A. شجرة بناء جملة مجردة المحددة مع الفصول الدراسية للقيام بكل العمل (لتبسيط Typechecking وتوليد الرموز الوسيطة) .. لذلك لدي فئة سلف ASTNode وجميع الطبقات النزعة مثل ASTFloat, ASTExpression, ASTIdentifier وما إلى ذلك وهلم جرا..

في .y ملف أنا قادر على بناء AST بالطريقة الشائعة:

nexp:
T_LPAR nexp T_RPAR { $$ = $2; }
| nexp OP_PLUS nexp { $$ = new ASTBExpression('+', (ASTExpression*)$1, (ASTExpression*)$3); }
| nexp OP_MINUS nexp { $$ = new ASTBExpression('-', (ASTExpression*)$1, (ASTExpression*)$3); }
| nexp OP_TIMES nexp { $$ = new ASTBExpression('*', (ASTExpression*)$1, (ASTExpression*)$3); }

ويعمل بشكل جيد للغاية ولكن بعد ذلك حاولت توليد بيانات نطاق (على سبيل المثال جسم إذا بيان) بهذه الطريقة: لقد استخدمت فئة ASTStatements التي لديها قائمة من ASTNode* يجب أن تملأ المحلل مع كل بيان واجهته.

لذلك سيكون النهج شيئا مشابها لهذا:

statements:
statement { if ($$ == null) $$ = new ASTStatements(); ((ASTStatements*)$$)->addStatement($1); } statements { $$->generateASM(); }
;

المشكلة هي أنه يجب تهيئة العنصر مرة واحدة فقط لكل كتلة من العبارات لكنني لا أعرف كيفية القيام بذلك. استخدام if ($$ == null) هو الاختراق حاولت ولكنها لا تعمل بسبب yylval يمكن أن تحتوي على أي ما يصل إلى هذه النقطة.

ما هي طريقة طبيعية / أفضل طريقة للتعامل مع هذا النوع من المواقف باستخدام Bison؟

Answer 1

قمت بحل هذه المشكلة عن طريق توليد ليست قائمة بالبيانات ولكن شجرة تدهور. لذلك كائن الفصل المعني هو:

ASTStatements
{
    ASTStatements *m_next;
    ASTStatement *m_statement;

    ....

    public:
        ASTStatements(ASTStatement *statement) // used for last one
        ASTStatements(ASTStatement *stat, ASTStatements *next) // used with a next one
}

باستخدام القواعد في .y بالطريقة الآتية:

statements: /* empty */ { $$ = null; }
| statements statement { if ($1 == null) $$ = new ASTStatements($2); else $$ = new ASTStatements($2, (ASTStatements*)$1); }

وبالفعل هذا هو اليسار العريض، مما يسمح بتصميم البيانات التي يجب تقليلها في أقرب وقت ممكن دون تشوش المكدس. تابعت نفس النهج لأي نوع آخر من "قائمة الرموز" المشاركة في لغتي ..

Answer 2

جرب قويما معدنا مثل ما يلي:

statements: statement { $$ = new ASTStatements();
                       ((ASTStatements*)$$)->addStatement($1); }      
 | statements statement { ((ASTStatements*)$$)->addStatement($2); }

لست متأكدا ما إذا كان هذا سوف يساعد.

Answer 3

هناك أسباب مختلفة لتفضيل القواعد المتردة ل YACC، لأي شيء يمكن أن تقلل في أقرب وقت ممكن في المدخلات.

في أي حال، عند القيام بذلك، يمكنك بعد ذلك استخدام نمط مثل هذا:

statements:                { $$ = new ... }
    | statements statement { /* now $1 and $2 do just what you want */ }
    ;