قواعد الأسبقية البسيطة

• احسب جدول علاقات أسبقية ويرث-ويبر لقواعد نحوية ذات رمز ابتدائي S.
• قم بتهيئة مكدس باستخدام علامة البداية $.
• أضف علامة نهاية $ إلى السلسلة التي يتم تحليلها ( المدخلات ).
• حتى يصبح Stack يساوي "$ S" ويصبح Input يساوي "$"
  • ابحث في الجدول عن العلاقة بين Top(stack) و NextToken(Input)
  • إذا كانت العلاقة ⋖ أو ≐
    • يحول :
    • دفع (المكدس، العلاقة)
    • دفع (المكدس، الرمز التالي (الإدخال))
    • RemoveNextToken(Input)
  • إذا كانت العلاقة ⋗
    • يقلل :
    • SearchProductionToReduce(Stack)
    • قم بإزالة المحور من المكدس
    • ابحث في الجدول عن العلاقة بين الرمز غير الطرفي من قاعدة الإنتاج وأول رمز في المكدس (بدءًا من الأعلى)
    • دفع (المكدس، العلاقة)
    • دفع (المكدس، غير طرفي)

SearchProductionToReduce (Stack)

• ابحث عن الرمز ⋖ العلوي في المكدس؛ هذا الرمز وجميع الرموز التي تعلوه هي المحور .
• أوجد قاعدة الإنتاج للقواعد النحوية التي يكون فيها المحور هو الجانب الأيمن.

بافتراض وجود لغة برمجة، يمكنها تحليل التعبيرات الحسابية التي تتضمن عمليات الضرب والجمع:

E --> E + T' | T' تي --> تي ص --> ص * خ | خ F --> ( E' ) | رقم E' --> E 

num هو رمز طرفي، ويقوم المحلل اللغوي بتحليل أي عدد صحيح على أنه num ؛ يمثل E تعبيرًا حسابيًا، وT هو حد و F هو عامل.

وجدول التحليل:

${\displaystyle G=\langle V_{n},V_{t},S,P\rangle }$

${\displaystyle {\begin{aligned}X\doteq Y&\iff {\begin{cases}A\to \alpha XY\beta \in P\\A\in V_{n}\\\alpha ,\beta \in (V_{n}\cup V_{t})^{*}\\X,Y\in (V_{n}\cup V_{t})\end{cases}}\\X\lessdot Y&\iff {\begin{cases}A\to \alpha XB\beta \in P\\B\Rightarrow ^{+}Y\gamma \\A,B\in V_{n}\\\alpha ,\beta ,\gamma \in (V_{n}\cup V_{t})^{*}\\X,Y\in (V_{n}\cup V_{t})\end{cases}}\\X\gtrdot Y&\iff {\begin{cases}A\to \alpha BY\beta \in P\\B\Rightarrow ^{+}\gamma X\\Y\Rightarrow ^{*}a\delta \\A,B\in V_{n}\\\alpha ,\beta ,\gamma ,\delta \in (V_{n}\cup V_{t})^{*}\\X,Y\in (V_{n}\cup V_{t})\\a\in V_{t}\end{cases}}\end{aligned}}}$

سنحدد ثلاث مجموعات للرمز:

${\displaystyle {\begin{aligned}\mathrm {Head} ^{+}(X)&=\{Y\mid X\Rightarrow ^{+}Y\alpha \}\\\mathrm {Tail} ^{+}(X)&=\{Y\mid X\Rightarrow ^{+}\alpha Y\}\\\mathrm {Head} ^{*}(X)&=(\mathrm {Head} ^{+}(X)\cup \{X\})\cap V_{t}\end{aligned}}}$

Head ^* ( X ) هي X إذا كان X رمزًا طرفيًا، وإذا كان X رمزًا غير طرفي، فإن Head ^* ( X ) هي المجموعة التي تضم الرموز الطرفية فقط التي تنتمي إلى Head ⁺ ( X ). هذه المجموعة مكافئة للمجموعة الأولى أو Fi( X ) الموصوفة في محلل LL .

الرأس ⁺ ( X ) والذيل ⁺ ( X ) يكونان ∅ إذا كان X طرفيًا.

الشفرة الزائفة لحساب العلاقات هي:

• RelationTable  := ∅
• لكل إنتاج${\displaystyle A\to \alpha \in P}$
  • لكل رمزين متجاورين XY في α
    • أضف (جدول العلاقات،${\displaystyle X\doteq Y}$)
    • أضف (جدول العلاقات،${\displaystyle X\lessdot \mathrm {Head} ^{+}(Y)}$)
    • أضف (جدول العلاقات،${\displaystyle \mathrm {Tail} ^{+}(X)\gtrdot \mathrm {Head} ^{*}(Y)}$)
• أضف (جدول العلاقات،${\displaystyle \$\lessdot \mathrm {Head} ^{+}(S)}$) حيث S هو الحرف غير الطرفي الأولي للقواعد، و$ هو علامة حد
• أضف (جدول العلاقات،${\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \$}$) حيث S هو الحرف غير الطرفي الأولي للقواعد، و$ هو علامة حد

${\displaystyle \lessdot }$و${\displaystyle \gtrdot }$يتم استخدامها مع المجموعات بدلاً من العناصر كما تم تعريفها، وفي هذه الحالة يجب عليك إضافة جميع الضرب الديكارتي بين المجموعات/العناصر.

${\displaystyle S\to aSSb|c}$

• الرأس ⁺ ( أ ) = ∅
• الرأس ⁺ ( S ) = { a, c }
• الرأس ⁺ ( ب ) = ∅
• الرأس ⁺ ( ج ) = ∅
• الذيل ⁺ ( أ ) = ∅
• الذيل ⁺ ( S ) = { b, c }
• الذيل ⁺ ( ب ) = ∅
• الذيل ⁺ ( ج ) = ∅
• الرأس ^* ( أ ) = أ
• Head ^* ( S ) = { a, c }
• الرأس ^* ( ب ) = ب
• الرأس ^* ( ج ) = ج
• ${\displaystyle S\to aSSb}$
  • أ بجوار S
    • ${\displaystyle a\doteq S}$
    • ${\displaystyle a\lessdot \mathrm {Head} ^{+}(S)}$
      • ${\displaystyle a\lessdot a}$
      • ${\displaystyle a\lessdot c}$
  • S بجوار S
    • ${\displaystyle S\doteq S}$
    • ${\displaystyle S\lessdot \mathrm {Head} ^{+}(S)}$
      • ${\displaystyle S\lessdot a}$
      • ${\displaystyle S\lessdot c}$
    • ${\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(S)}$
      • ${\displaystyle b\gtrdot a}$
      • ${\displaystyle b\gtrdot c}$
      • ${\displaystyle c\gtrdot a}$
      • ${\displaystyle c\gtrdot c}$
  • S بجوار b
    • ${\displaystyle S\doteq b}$
    • ${\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(b)}$
      • ${\displaystyle b\gtrdot b}$
      • ${\displaystyle c\gtrdot b}$
• ${\displaystyle S\to c}$
  • يوجد رمز واحد فقط، لذلك لا تتم إضافة أي علاقة.

جدول الأسبقية

${\displaystyle {\begin{array}{c|ccccc}&S&a&b&c&\$\\\hline S&\doteq &\lessdot &\doteq &\lessdot &\\a&\doteq &\lessdot &&\lessdot &\\b&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\c&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\\$&&\lessdot &&\lessdot &\end{array}}}$

${\displaystyle S\to a|aT|[S]}$

${\displaystyle T\to b|bT}$

• الرأس ⁺ ( S ) = { a, [ }
• الرأس ⁺ ( أ ) = ∅
• الرأس ⁺ ( T ) = { b }
• الرأس ⁺ ( [ ) = ∅
• الرأس ⁺ ( ] ) = ∅
• الرأس ⁺ ( ب ) = ∅

• الذيل ⁺ ( S ) = { a, T, ], b }
• الذيل ⁺ ( أ ) = ∅
• الذيل ⁺ ( T ) = { b, T }
• الذيل ⁺ ( [ ) = ∅
• الذيل ⁺ ( ] ) = ∅
• الذيل ⁺ ( ب ) = ∅

• Head ^* ( S ) = { a, [ }
• الرأس ^* ( أ ) = أ
• الرأس ^* ( T ) = { b }
• الرأس ^* ( [ ) = [
• الرأس ^* ( ] ) = ]
• الرأس ^* ( ب ) = ب

• ${\displaystyle S\to aT}$

• • أ بجوار تي
    • ${\displaystyle a\doteq T}$
    • ${\displaystyle a\lessdot \mathrm {Head} ^{+}(T)}$
      • ${\displaystyle a\lessdot b}$

• ${\displaystyle S\to [S]}$

• • [ بجوار S]
    • ${\displaystyle [\doteq S}$
    • ${\displaystyle [\lessdot \mathrm {Head} ^{+}(S)}$
      • ${\displaystyle [\lessdot a}$
      • ${\displaystyle [\lessdot [}$

• • S بجوار ]
    • ${\displaystyle S\doteq ]}$
    • ${\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(])}$
      • ${\displaystyle a\gtrdot ]}$
      • ${\displaystyle T\gtrdot ]}$
      • ${\displaystyle ]\gtrdot ]}$
      • ${\displaystyle b\gtrdot ]}$

• ${\displaystyle T\to bT}$

• • ب بجوار تي
    • ${\displaystyle b\doteq T}$
    • ${\displaystyle b\lessdot \mathrm {Head} ^{+}(T)}$
      • ${\displaystyle b\lessdot b}$

جدول الأسبقية

${\displaystyle {\begin{array}{c|ccccccc}&S&T&a&b&[&]&\$\\\hline S&&&&&&\doteq &\doteq \\T&&&&&&\gtrdot &\gtrdot \\a&&\doteq &&\lessdot &&\gtrdot &\gtrdot \\b&&\doteq &&\lessdot &&\gtrdot &\gtrdot \\{\text{[}}&\doteq &&\lessdot &&\lessdot &&\\]&&&&&&\gtrdot &\gtrdot \\\$&\doteq &&\lessdot &&\lessdot &&\end{array}}}$