تحليل النسب العودي - من LL (1) إلى الأعلى

Question

يمكن تحليل قواعد "تعبير الآلة الحاسبة" البسيطة التالية (BNF) بسهولة باستخدام محلل النسب العودي التافه، وهو تنبؤي LL(1):

<expr>      :=  <term> + <term>
            |   <term> - <term>
            |   <term>
<term>      :=  <factor> * <factor>
                <factor> / <factor>
                <factor>
<factor>    :=  <number>
            |   <id>
            |   ( <expr> )
<number>    :=  \d+
<id>        :=  [a-zA-Z_]\w+

لأنه يكفي دائمًا رؤية الرمز المميز التالي لمعرفة القاعدة التي يجب اختيارها.ومع ذلك، لنفترض أنني أضفت القاعدة التالية:

<command>   :=  <expr>
            |   <id> = <expr>

لغرض التفاعل مع الآلة الحاسبة في سطر الأوامر، مع المتغيرات، مثل هذا:

calc> 5+5
=> 10
calc> x = 8
calc> 6 * x + 1
=> 49

هل صحيح أنني لا أستطيع استخدام محلل تنبؤي بسيط LL(1) للتحليل <command> قواعد ؟حاولت أن أكتب المحلل اللغوي لذلك، ولكن يبدو أنني بحاجة إلى معرفة المزيد من الرموز المميزة في المستقبل.هل الحل هو استخدام التراجع، أم يمكنني فقط تنفيذ LL(2) والتطلع دائمًا إلى رمزين مميزين؟

كيف تتعامل مولدات المحلل اللغوي RD مع هذه المشكلة (ANTLR، على سبيل المثال)؟

Answer 1

المشكلة مع

<command>   :=  <expr>
            |   <id> = <expr>

هل هذا عندما "ترى" <id> لا يمكنك معرفة ما إذا كانت هذه بداية مهمة (القاعدة الثانية) أم أنها "<factor>".ستعرف فقط متى ستقرأ الرمز المميز التالي.

AFAIK ANTLR هو LL(*) (وهو أيضًا قادر على إنشاء موزعي حزمة الفئران إذا لم أكن مخطئًا) لذلك من المحتمل أن يتعامل مع هذه القواعد مع الأخذ في الاعتبار رمزين مميزين في وقت واحد.

إذا كان بإمكانك اللعب بالقواعد، فإنني أقترح إما إضافة كلمة رئيسية للمهمة (على سبيل المثال: let x = 8) :

<command>   :=  <expr>
            |   "let" <id> "=" <expr>

أو استخدم = للدلالة على التقييم:

<command>   :=  "=" <expr>
            |   <id> "=" <expr>

Answer 2

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

انظر الى الامام

command() {
    if (currentToken() == id && lookaheadToken() == '=') {
        return assignment();
    } else {
        return expr();
    }
}

التراجع

command() {
    savedLocation = scanLocation();
    if (accept( id )) {
         identifier = acceptedTokenValue();
         if (!accept( '=' )) {
             setScanLocation( savedLocation );
             return expr();
         }
         return new assignment( identifier, expr() );
    } else {
         return expr();
    }
}

Answer 3

المشكلة هي أن النحو:

<command>   :=  <expr>
            |   <id> = <expr>

ليس إجراءً متكررًا بشكل متبادل.للحصول على محلل لائق عودي، ستحتاج إلى تحديد مكافئ غير عودي.

يُظهر منشور rdentato كيفية حل هذه المشكلة، على افتراض أنه يمكنك اللعب بالقواعد.يوضح هذا PowerPoint المشكلة بمزيد من التفاصيل ويوضح كيفية تصحيحها:http://www.google.com/url?sa=t&source=web&ct=res&cd=7&url=http%3A%2F%2Fxml.cs.nccu.edu.tw%2Fcourses%2Fcompiler%2Fcp2006%2Fslides%2Flec3-Parsing% 26TopDownParsing.ppt&ei=-YLaSPrWGaPwhAK5ydCqBQ&usg=AFQjCNGAFrODJxoxkgJEwDMQ8A8594vn0Q&sig2=nlYKQVfakmqy_57137XzrQ

Answer 4

أنتلر 3 يستخدم محلل "LL(*)" بدلاً من محلل LL(k)، لذلك سوف يتطلع إلى الأمام حتى يصل إلى نهاية الإدخال إذا كان عليه ذلك، دون التراجع، باستخدام أتمتة حتمية محددة محسنة خصيصًا (DFA) .