Oddiy ustunlik tahlilchisi - Simple precedence parser

Yilda Kompyuter fanlari, a oddiy ustunlik tahlilchisi ning bir turi pastdan yuqoriga qarab tahlil qiluvchi uchun kontekstsiz grammatikalar faqat tomonidan ishlatilishi mumkin oddiy ustunlik grammatikalari.

Tahlilchining amalga oshirilishi umumiyga juda o'xshash pastdan yuqoriga qarab tahlil qiluvchi. Stack a saqlash uchun ishlatiladi yashovchan prefiks a yuborilgan shakl dan o'ng tomondan hosil qilish. Belgilar , va aniqlash uchun ishlatiladi pivotva qachon bo'lishini bilish Shift yoki qachon Kamaytirish.

Amalga oshirish

  • Hisoblang Wirth-Weberning ustuvorligi stol.
  • Faqat bilan birikma bilan boshlang boshlang'ich marker $.
  • Ip ajratilganidan boshlang (Kiritish) bilan tugadi tugaydigan marker $.
  • Bo'lmasa ham (Stack $ S ga, Kiritish $ ga teng) (S = Grammatikaning boshlang'ich belgisi)
    • Top (stack) va NextToken (Input) o'rtasidagi munosabatlarni jadvaldan qidirish
    • agar munosabatlar bo'lsa yoki
      • Shift:
      • Push (Stack, munosabatlar)
      • Push (Stack, NextToken (Input))
      • RemoveNextToken (Kirish)
    • agar munosabatlar bo'lsa
      • Kamaytirish:
      • SearchProductionToReduce (Stack)
      • RemovePivot (Stack)
      • Ishlab chiqarishdagi Non terminal va stekdagi birinchi belgi o'rtasidagi munosabatni jadvaldan qidiring (Yuqoridan boshlab)
      • Push (Stack, munosabatlar)
      • Push (Stack, Terminal bo'lmagan)

SearchProductionToReduce (Stack)

  • qidirish Pivot stekka eng yaqin tepadan
  • grammatikani ishlab chiqarishda qaysi tomoni bir xil o'ng tomonga ega bo'lsa, qidirish Pivot

Misol

Tilni hisobga olgan holda:

E -> E + T '| T'T '-> TT -> T * F | FF -> (E ') | numE '-> E

num terminaldir va lexer sifatida har qanday butun sonni ajrating num.

va tahlil jadvali:

EE 'TT 'F+*()num$
E
E '
T
T '
F
+
*
(
)
num
$
QO'ShIMChA QABUL QILISh HARAKATI $ <2 * (1 + 3) $ SHIFT $ <2> * (1 + 3) $ REDUCE (F -> num) $  * (1 + 3) $ REDUCE (T -> F) $ ) + 3) $ 4 marta kamaytirish (F -> son) (T -> F) (T '-> T) (E -> T') $ ) $ REDUCE 3 marta (F -> num) (T -> F) (T '-> T) $ ) $ 2 marta kamaytiring (E -> E + T) (E '-> E) $  $ REDUCE (F -> (E')) $  $ REDUCE (T -> T * F) $  $ REDUCE 2 marta (T '-> T) (E -> T') $  $ QABUL

Adabiyotlar

  • Alfred V. Aho, Jeffri D. Ullman (1977). Kompilyatorni loyihalashtirish asoslari. 1-nashr. Addison-Uesli.
  • Uilyam A. Barret, Jon D. Kuch (1979). Tuzuvchi tuzilishi: Nazariya va amaliyot. Ilmiy tadqiqotlar bo'yicha mutaxassis.
  • Jan-Pol Tremblay, P. G. Sorenson (1985). Kompilyator yozish nazariyasi va amaliyoti. McGraw-Hill.