16. Анализ отдолу нагоре
Този раздел ще обсъди основната техника за разбор отдолу нагоре, известна като разбор с преместване и накратко наричана PS разбор. Лесен за внедряване вид PS анализ, наречен анализ с приоритет на оператора. PS анализът се опитва да изгради дърво за анализ за входен низ, започвайки от листата (отдолу) и работейки към корена на дървото (нагоре). Този процес може да се разглежда като навиване на низа w към началния знак на граматиката. На всяка стъпкаконволюциястъпка на намаляване) някакъв подниз, съответстващ на дясната страна на продукцията, се заменя със знак от лявата страна на тази продукция и ако на всяка стъпка поднизовете са избрани правилно, тогава получаваме обратното дясно генериране.
Има 3 основни понятия.
Стъблотона низ A е подниз, за който има правило в тази граматика
Конволюцияе замяната на основата с левия знак, правилата в изходната верига ( до B)
Прехвърляне– прехвърляне от входния низ към формата на стека на представянето на изходната верига.
bdc входен низ
PS анализатор (трансфер, конволюция)
СтекРеализация на PS-анализ
Има два проблема с анализирането чрез подрязване на стъблото. Първият е да намеря подниз, който да сгъна във форма на дясно изречение, и аз трябва да определя коя продукция трябва да бъде избрана, ако има само продукции със съответния подниз от дясната страна. Преди да отговорим на тези въпроси, нека първо да разгледаме структурите от данни, използвани в PS анализатора.
Доста удобен начин за прилагане на PS анализатор е да се използва стек за съхранение на граматични символи и входен буфер за съхраняване на анализираната граматика.линии. Използваме $ като маркер за дъното на стека и същият символ е маркерът за десния край на входния низ. Първоначално стекът е празен и входният буфер съдържа низаw.
Анализаторът работи, като избутва нула или повече символи в стека, докато стеблото β е отгоре на стека. След това той навива β
Лявата страна на съответните продукти. Анализаторът повтаря този цикъл, докато се срещне грешка или влезе в конфигурация, когато само началният знак е в стека и входният буфер е празен:
Веднъж в тази конфигурация, анализаторът спира и съобщава, че входният низ е бил анализиран успешно.