Елиминација једноструких правила
Нека је дата КС-граматика . Претпоставимо да је у граматици G нема некорисних симбола, ни ε-правила. Поступак елиминације једноструких правила се своди на поступак тражења свих извођења облика:[1]
Овај поступак се врши рекурзивно полазећи од једноструких правила. Кад год се пронађе извођење горњег облика, правилима која на левој страни имају X додају се десне стране свих правила која нису једнострука, а која на левој страни имају симбол Y, док се једнострука Y-правила уклањају. Овако трансформисана граматика може имати некорисних симбола, које треба елиминисати. Добијена граматика је еквивалентна полазној граматици, а нема некорисних симбола, као ни једноструких или ε-правила.
Пример[уреди | уреди извор]
У граматици ослобођеној од ε-правила:
- (1)
- (2)
једино једноструко извођење је . Заменом симбола S на десној страни правила (1) досном страном правила (2), добија се следећа граматика без једноструких правила:
- (1)
- (2)
Погледајте још[уреди | уреди извор]
Белешке[уреди | уреди извор]
- ^ Извор комплетног чланка: „Преводиоци и интерпретатори - увод у теорију и методе компилације програмских језика“ - Душко Витас.