ຜູ້ລວບລວມຂໍ້ມູນ: ຕົວແຕກຕ່າງລະຫວ່າງ LL (0) ແລະ LR (0) ຕົວແຍກຄວາມແຕກຕ່າງແມ່ນຫຍັງ? ມີສິ່ງດັ່ງກ່າວເປັນ LL (0) ຕົວກວດ?


ຕອບ 1:

ຄຳ ຖາມນີ້ເບິ່ງຄືວ່າຈະເອົາໃຈໃສ່ LL (0) ຕົວ ກຳ ມະກອນ, ສະນັ້ນໃຫ້ ກຳ ນົດມັນ. ເຄື່ອງຈັກແບ່ງປັນ LL (0) ແຍກຈາກຊ້າຍຫາຂວາດ້ວຍ 0 tokens ໃນຕອນເລີ່ມຕົ້ນຂອງການຜະລິດເພື່ອ ກຳ ນົດວ່າການຜະລິດໃດທີ່ຈະໃຊ້. ໝາຍ ເລກ 0 ນີ້ ໝາຍ ຄວາມວ່າແນວໃດ? ນີ້ ໝາຍ ຄວາມວ່ານັກວິເຄາະບໍ່ສາມາດໃຊ້ຂໍ້ຄວາມເພື່ອວິເຄາະເພື່ອ ກຳ ນົດການຜະລິດໃດທີ່ຈະໃຊ້. ນີ້ ໝາຍ ຄວາມວ່າຜູ້ຄັດເລືອກບໍ່ສາມາດເລືອກໄດ້. ມັນຈໍາເປັນຕ້ອງຮູ້ກ່ອນທີ່ມັນຈະເລີ່ມວິເຄາະຄໍາສັ່ງຂອງ tokens ທີ່ມັນຈະວິເຄາະ. ຄໍາສັ່ງຂອງ tokens ຕ້ອງຖືກກໍານົດ. ນີ້ ໝາຍ ຄວາມວ່າມັນສາມາດມີພຽງແຕ່ ໜຶ່ງ ຄຳ ສັ່ງທີ່ນັກວິເຄາະວິເຄາະ. ດັ່ງນັ້ນທ່ານອາດຈະມີຕົວຊີ້ບອກທີ່ເວົ້າວ່າ "ສະບາຍດີໂລກ!" ຍອມຮັບ. ມີໄວຍາກອນເຊັ່ນນີ້:

ເປົ້າ ໝາຍ: "ສະບາຍດີ" ອະວະກາດ "ໂລກ" ເຄື່ອງ ໝາຍ ອ້າງອີງ;

ໃຫ້ສັງເກດວ່າມີພຽງແຕ່ການປ່ຽນແປງກ່ຽວກັບວິທີທີ່ lexer ກົງກັບ tokens ໄດ້ຖືກອະນຸຍາດ.

(ຂ້າພະເຈົ້າຫວັງວ່າການສັງເກດແມ່ນຈະແຈ້ງ - ມັນແມ່ນສິ່ງທີ່ ຈຳ ເປັນທີ່ຂ້ອຍໃຊ້ໃນ Yacc ++. ສາຍທີ່ອ້າງອີງແມ່ນ tokens, ຄືກັບຕົວລະບຸຕົວຕົນທີ່ບໍ່ໄດ້ ກຳ ນົດ).

ຕົວແປພາສາສະເຫມີຄາດຫວັງວ່າຄໍາສັ່ງດຽວກັນຂອງ tokens. ບໍ່ ຈຳ ເປັນຕ້ອງມີກົດລະບຽບພຽງຢ່າງດຽວເທົ່າທີ່ຕົວຢ່າງ ທຳ ອິດຂອງພວກເຮົາໄດ້ເຮັດ. ມັນສາມາດເບິ່ງຄືວ່ານີ້.

ເປົ້າ ໝາຍ: ສະບາຍດີຕອນສິ້ນສ່ວນ;

ສະບາຍດີພາກສ່ວນ: Hallo1;

hello1: "ສະບາຍດີ";

ສິ້ນສຸດ: ສ່ວນຂອງໂລກສ່ວນສຸດທ້າຍ;

ພາກສ່ວນໂລກ: "ໂລກ";

ພາກສ່ວນສຸດທ້າຍ: "!";

ເຖິງຢ່າງໃດກໍ່ຕາມໃຫ້ສັງເກດວ່າບໍ່ມີກົດລະບຽບໃດໆປະກອບມີຜູ້ປະຕິບັດງານ "ຫລື" (|) ແລະມີກົດລະບຽບ ໜຶ່ງ ຕໍ່ ໜຶ່ງ ທີ່ບໍ່ແມ່ນຢູ່ປາຍທາງ. ວິທີນີ້, ຕົວແປສາມາດຮູ້ວິທີການສອດຄ່ອງກັບແຕ່ລະກົດໂດຍບໍ່ຕ້ອງໃຊ້ tokens ທີ່ ຈຳ ແນກ (tokens ທີ່ເລືອກທິດທາງໃດທີ່ parser ໄປ), ເຮັດໃຫ້ຫລັກໄວຍາກອນ LL (0).

ດຽວນີ້ມັນສາມາດ ນຳ ໃຊ້ການຜະລິດແບບທົດແທນແລະຍັງມີໄວຍາກອນ LL (0) ບໍ? ຄຳ ຕອບແມ່ນບໍ່, ໃຫ້ເຮົາເບິ່ງວ່າຈະມີຫຍັງເກີດຂື້ນຖ້າພວກເຮົາມີກົດລະບຽບທີ່ເອີ້ນຄືນ.

ເປົ້າ ໝາຍ: "x" ເປົ້າ ໝາຍ "y";

ຈົ່ງຈື່ໄວ້ວ່າພວກເຮົາພຽງແຕ່ອະນຸຍາດໃຫ້ໃຊ້ກົດລະບຽບ ໜຶ່ງ ຕໍ່ ໜຶ່ງ ປາຍຄົນແລະບໍ່ມີຜູ້ປະຕິບັດງານ "ຫລື". ສະນັ້ນເມື່ອພວກເຮົາໄດ້ຮັບການເອີ້ນທີ່ຮຽກຮ້ອງຄືນເພື່ອເປົ້າ ໝາຍ, ພວກເຮົາຕ້ອງຊອກຫາວິທີທີ່ຈະກັບຄືນມາຫາການເອີ້ນທີ່ເອີ້ນຄືນ, ວົງການທີ່ບໍ່ມີວັນສິ້ນສຸດ. ພິສູດຕົວທ່ານເອງ, ມັນບໍ່ ສຳ ຄັນວ່າພວກເຮົາຮວບຮວມສາຍນີ້ຫລືການຮ້ອງຂໍການເອີ້ນຄືນໂດຍທາງອ້ອມ. ສິ່ງນີ້ຈະ ນຳ ໄປສູ່ວົງຈອນທີ່ບໍ່ມີສິ້ນສຸດ.

ສະນັ້ນ, ຫຼັກສູດ LL (0) ຫຼັກໄວຍາກອນຕ້ອງວິເຄາະບັນຊີລາຍຊື່ທີ່ ຈຳ ກັດຂອງໂທເຄນ, ແນ່ນອນແມ່ນລາຍຊື່ທີ່ ຈຳ ກັດ (ບັນຊີດຽວກັນທຸກໆຄັ້ງ).

ໃຫ້ສັງເກດຄວາມແຕກຕ່າງໃນຄວາມ ໝາຍ ຂອງ LR (0). ຕົວແຍກ LR (k) ອາດຈະໃຊ້ ຈຳ ນວນ tokens ໃດ ໜຶ່ງ ພາຍໃນການຜະລິດເພື່ອ ຈຳ ແນກມັນ, ບວກກັບ k tokens ຈາກສະພາບການທີ່ການຜະລິດຫຼຸດລົງເພື່ອ ກຳ ນົດວ່າມັນຄວນຈະຫຼຸດລົງຫຼືບໍ່. ໃນກໍລະນີ LR (0), ບໍ່ມີ tokens ເພີ່ມເຕີມສາມາດໃຊ້ເພື່ອຕັດສິນໃຈວ່າຈະຫຼຸດຜ່ອນມັນ. ມັນພຽງແຕ່ຕ້ອງໄດ້ຕັດສິນໃຈໂດຍອີງໃສ່ໂທເຄນທີ່ຖືກຫຼຸດລົງຕາມປົກກະຕິ. ນີ້ແມ່ນໄວຍາກອນ LR (0) ຫຼັກ:

ເປົ້າ ໝາຍ: "x" | "(" "ປະຕູຮົ້ວ") ";

ຫລັກໄວຍາກອນນີ້ແຍກ "x" ອ້ອມຮອບໄປດ້ວຍວົງເລັບຕ່າງໆ. ໃຫ້ສັງເກດວ່າ token "x" ແລະ token "(" ສາມາດໃຊ້ເພື່ອຕັດສິນໃຈວ່າກົດລະບຽບໃດທີ່ຈະໃຊ້. 0 ໃນ LR (0) ບໍ່ໄດ້ ຈຳ ກັດການໃຊ້ tokens ພາຍໃນກົດລະບຽບ, ເຊັ່ນດຽວກັບ 0 ໃນ LL (0) ສິ່ງດຽວທີ່ ຈຳ ກັດມັນແມ່ນການໃຊ້ tokens (ຕາມສະພາບການ, ໂດຍປົກກະຕິ ສຳ ລັບການໃຊ້ສາຍທີ່ບໍ່ແມ່ນສະຖານີ) ເມື່ອທ່ານເລືອກການຫຼຸດຜ່ອນ, ໄວຍາກອນນີ້ບໍ່ ຈຳ ເປັນຕ້ອງມີສະພາບການໃດໆ, ໃນທາງເລືອກ ທຳ ອິດ, ມັນຈະຖືກຫຼຸດລົງໂດຍການເຫັນ "x" ທີສອງທີ່ມັນຫຼຸດລົງຫຼັງຈາກເຫັນ ")". tokens ພາຍໃນກົດລະບຽບ ກຳ ນົດຢ່າງແນ່ນອນວ່າຄວນຈະຫຼຸດຜ່ອນກົດລະບຽບໃນເວລາໃດ.


ຕອບ 2:

ຕົວຊີ້ບອກ LL (0) ໝາຍ ຄວາມວ່າພວກເຂົາປຸງແຕ່ງກະແສສັນຍາລັກຈາກຊ້າຍຫາຂວາ, ໂດຍໃຊ້ອະນຸພັນເບື້ອງຊ້າຍໄກໂດຍບໍ່ໄດ້ເບິ່ງເຫັນລ່ວງ ໜ້າ. ໃນທາງທິດສະດີ, LL (0) ແມ່ບົດວິເຄາະແມ່ນເປັນໄປໄດ້, ແຕ່ເຖິງແມ່ນວ່າມັນມີຢູ່, ຂ້ອຍບໍ່ເຫັນວ່າມີການ ນຳ ໃຊ້ຫຼາຍປານໃດ ສຳ ລັບພວກມັນ. LL (0) ຕົວຊີ້ບອກຈະຕ້ອງຄາດຄະເນວ່າຜະລິດຕະພັນໃດທີ່ຈະໃຊ້ໂດຍອີງໃສ່ສະຖານີທີ່ບໍ່ແມ່ນປະຈຸບັນທີ່ມີສາຍຕາລ່ວງ ໜ້າ. ໃນ grammars ດັ່ງກ່າວ, ມີພຽງແຕ່ການຜະລິດ ໜຶ່ງ ເທົ່ານັ້ນທີ່ສາມາດຖືກມອບ ໝາຍ ໃຫ້ແຕ່ລະຄົນທີ່ບໍ່ແມ່ນສະຖານີ, ແລະບໍ່ຄວນມີການເອີ້ນຄືນອີກ.

ຕົວຊີ້ບອກ LR (0) ໝາຍ ຄວາມວ່າພວກເຂົາ ດຳ ເນີນການສາຍ token ຈາກຊ້າຍຫາຂວາ, ໂດຍໃຊ້ອະນຸພັນຢູ່ເບື້ອງຂວາມືໂດຍມີມຸມມອງໄປທາງ ໜ້າ. ນີ້ ໝາຍ ຄວາມວ່າພວກເຂົາສ້າງຕົ້ນໄມ້ວິເຄາະຕັ້ງແຕ່ລຸ່ມຫາເທິງ, ໃນຂະນະທີ່ຕົວຊີ້ບອກ LL (0) ກໍ່ສ້າງຕົ້ນໄມ້ວິເຄາະຈາກດ້ານເທິງຫາລຸ່ມ.