Нормална форма Грибах
У рачунарству, за контекстно-слободну граматику се каже да је у нормалној форми Грибах (ГНФ), ако су сва њена правила извођења облика:
или
где је -{A}- нетерминални симбол, α је терминални симбол, -{X}- је (можда празан) низ нетерминалних симбола искључујући почетни симбол, -{S}- је почетни симбол, а -{λ}- је празан стринг.
Из овога следи да је граматика која је у нормалној форми Грибах без левих рекурзија.
Свака контекстно-слободна граматика може да се трансформише у еквивалентну граматику у нормалној форми Грибах. (Неке дефиниције не дозвољавају други од наведена два облика правила извођења, у ком случају контекстно-слободна граматика која може да генерише празну ниску не може да се трансформише у нормалну форму Грибах.) Ово може да се користи за доказ да сваки контекстно-слободни језик може да буде препознат од стране недетерминистичког потисног аутомата.
За дату граматику у ГНФ и ниску дужине -{n}-, изводљиву у тој граматици, сваки топ-даун парсер ће стати на дубини -{n}-.
Нормална форма Грибах је добила име по Шили Грибах.
Види још
Литература
- -{John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. Шаблон:ISBN. (See chapter 4.)}-
- Душко М. Витас, Преводиоци и интерпретатори (Увод у теорију и методе компилације програмских језика), Математички факултет, Београд, 2006'