Jump to content

Talk:Shift-reduce parser

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Decicion Conflicts

[edit]

There are many occurrences when a shift-reduce parser could apply several reduce rules, or both a shift and a reduce rule. How these conflicts are handled is an important distinction between different types of shift-reduce parsers.

The article states:

The parser keeps applying reductions to the top of the parse stack for as long as it keeps finding newly completed examples of grammar rules there. When no more rules can be applied, the parser then shifts the lookahead symbol onto the parse stack, scans a new lookahead symbol, and tries again.

This is somewhat inaccurrate. Consider the following grammar:

Sum -> number | number + Sum

After reading a number, the parser cannot just reduce it to a sum, it has to shift if what follows is a plus sign. --Jonas Wagner (talk) 13:34, 25 July 2012 (UTC)[reply]

citation needed

[edit]

what is citation? how to find correct one? NewsWork (talk) 18:14, 9 May 2020 (UTC)[reply]

Other parser methods that backtrack may take exponential time when they guess badly. NewsWork (talk) 18:18, 9 May 2020 (UTC)[reply]

above line in : Parser Actions NewsWork (talk) 18:20, 9 May 2020 (UTC)[reply]

Do not omit "implicit" information?

[edit]

I find in many Wikipedia articles that a lot of knowledge is implied, but not in a way where, say, it benefits much (i.e. where cost of having to explain additional terms and concepts would be prohibitive or counterproductive). Case in point is in section "Tree building steps" in the article where tokens "A", "B", "C" and "2" are implied with "id" and "int", although one may argue that the concept of terminals vs. non-terminals, and how terminals (which are called that for a reason) _form_ non-terminals through production rules, should not be omitted from an article that covers parsing.

What I'd propose is further detail list of steps in the section clarifying how "A", "B", etc, are reduced to "id", "int". It would not make for a much longer list (and if it were, it only would underpin the very utility of having such a list explicit in the first place) and I must admit as someone still coming back to the article to refresh my still fresh and developing knowledge of parsing, I think about this very flaw in the article, every time. Transientdifficulties (talk) 14:02, 6 April 2023 (UTC)[reply]