/docs/MyDocs

To get this branch, use:
bzr branch http://darksoft.org/webbzr/docs/MyDocs

« back to all changes in this revision

Viewing changes to Development/parsers/lr_parser.txt

  • Committer: Suren A. Chilingaryan
  • Date: 2009-04-09 03:21:08 UTC
  • Revision ID: csa@dside.dyndns.org-20090409032108-w4edamdh4adrgdu3
import

Show diffs side-by-side

added added

removed removed

Lines of Context:
Development/parsers/lr_parser.txt
 
1
Formal Grammar  - is a precise description of a formal language - that is, of a
 
2
--------------  set of strings over some alphabet.
 
3
    - Generative Grammars - describe how to write strings that belong to a 
 
4
    given language. Consists of a start symbol and a set of rules for 
 
5
    transforming strings. The language consists of all the strings that can 
 
6
    be generated in this manner. Example:
 
7
        * S is starting symbol (non-terminal symbol)
 
8
        * Rules: S -> aSb, S->ab
 
9
        + S symbol is not mandatory belongs to language. In that case to 
 
10
        language belongs all produced strings without S. In that case
 
11
            ab, aabb, aaabbb, ...
 
12
        + Actually, it is possible to have several starting/non-terminal
 
13
        symbols
 
14
    - Aanalytic Grammars - describe how to recognize when strings are members 
 
15
    in the language
 
16
    Wiki: http://en.wikipedia.org/wiki/Formal_grammar
 
17
 
 
18
Context-Free Grammar - is a grammar in which every production rule is of the 
 
19
-------------------- form: V -> w
 
20
    V is a single nonterminal symbol
 
21
    w is a string of terminals and/or nonterminals 
 
22
 
 
23
    + The term "context-free" expresses the fact that nonterminals can be 
 
24
    rewritten without regard to the context in which they occur.
 
25
 
 
26
 
 
27
Derivation - There are two common ways to describe how a given string can be 
 
28
---------- derived from the start symbol of a given grammar.
 
29
 a) List the consecutive strings of symbols, beginning with the start symbol 
 
30
 and ending with the string, and the rules that have been applied.
 
31
 b) Define a derivation strategy, for example in:
 
32
    Leftmost/Rightmost Derivation - the rules are applied following the 
 
33
    strategy: 'always replace the left/right-most nonterminal first'
 
34
    + In this case list of applied grammar rules is by itself sufficient.
 
35
    + Example for rightmost derivation:
 
36
        rules: (1) S -> S + S, (2) S -> 1, (3) S -> a
 
37
        string: "1 + 1 + a"
 
38
        the transformation: (1), (1), (2) (2) (3)
 
39
        S -> S + S -> S + (S + S) -> S + S + a -> S + 1 + a -> 1 + 1 + a
 
40
 c) ambiguous grammar - if there is some string that it can generate in more 
 
41
 than one way
 
42
 
 
43
 
 
44
Grammar Parsers (live demo)
 
45
---------------
 
46
 1. We have symbols of language 
 
47
    a) Operators: +-/*
 
48
    b) Parenthesis: ()
 
49
    c) Assignment Operator: =
 
50
    d) Numbers: N
 
51
    e) Variables: V
 
52
 2. We have a set of rules how the strings (statements) of our language 
 
53
 can be constructed (and we now how to process them!).
 
54
    1-4.        S->S+S, S->S-S, S->S*S, S->S/S
 
55
    5.          S->(S)
 
56
    6.          S->V=S
 
57
    7.          S->NUM
 
58
    8.          S->V
 
59
 3. We have a string in our formal language: 'V = N * (N + N)'. We actually
 
60
 want to get a sequence of simple operations (which we no how to process), 
 
61
 to derive our actual string. 
 
62
 In the case of rightmost derivation:
 
63
     (6)        V = S 
 
64
     (3)        V = S * S
 
65
     (5)        V = S * (S)
 
66
     (1)        V = S * (S + S)
 
67
     (7)        V = S * (S + N)
 
68
     (7)        V = S * (N + N)
 
69
     (7)        V = N * (N + N)
 
70
 4. We know hot to perform all operations from (2), and perform them from 
 
71
 bottom to top
 
72
        V = 5 * (4 + 3)
 
73
        V = 5 * (7)
 
74
        V = 35
 
75
        assigning V
 
76
 5. If there are ambiguity and we can do two different derivations, then we
 
77
 don't know which of possible operation sequence we actually should perform.
 
78
 - For exmaple if we have following actual string: 'V = N * N + N', there are
 
79
 existing two different sequences producing this string from S:
 
80
            V = S                       V = S
 
81
            V = S * S                   V = S + S
 
82
            V = S * S + S               V = S + N
 
83
            V = S * S + N               V = S * S + N
 
84
            ...                         ....
 
85
 - And we would get different results, If we perform operations with given 
 
86
 above symantec:
 
87
            V = 5 * 4 + 3               V = 5 * 4 + 3       
 
88
            V = 5 * 7                   V = 20 + 3
 
89
            V = 35                      V = 23
 
90
 
 
91
 
 
92
Bottom-Top Parsers
 
93
==================
 
94
LL parser - is a parser for context-free grammars that reads input from left 
 
95
to right and produces a Leftmost derivation.
 
96
 
 
97
LR parser - is a parser for context-free grammars that reads input from left 
 
98
to right and produces a Rightmost derivation.
 
99
    * LR(k) - parser is also used; here the k refers to the number of 
 
100
    unconsumed "look ahead" input symbols that are used in making parsing 
 
101
    decisions. LR by default means LR(1)
 
102
    * A context-free grammar is called LR(k) if there exists an LR(k) parser 
 
103
    for it.
 
104
 
 
105
    Depending on how the parsing table is generated, there are separated 
 
106
    several types of LR parsers (all this parsers are able to parse only a 
 
107
    limited subset of valid LR grammars)
 
108
 
 
109
    'First Set', 'Follow Set' 
 
110
    -------------------------
 
111
    For each string of Language there are defined two sets of symbols (of that
 
112
    language) FIRST(STR), FOLLOW(STR) which are formed by special rules. The
 
113
    rules are listed there: 
 
114
        http://www.jambe.co.nz/UNI/FirstAndFollowSets.html
 
115
    
 
116
    SLR (Simple LR parser)
 
117
        Parsing tables are generated as for an LR(0) parser except that it only
 
118
        performs a reduction with a grammar rule A -> w, if the next symbol 
 
119
        on the input stream is in FOLLOW(A)
 
120
        Example, grammar parsable by SLR, but not LR(0)
 
121
            rules: S -> 1 S, S -> 1
 
122
            
 
123
    LALR (Look-ahead LR parser)
 
124
        + Can deal with more grammars when SLR does
 
125
        + Gives a good trade-off between the number of grammars it can deal 
 
126
        with and the size of the parsing tables it requir
 
127
        + Using Lookahead sets instead of follow sets.
 
128
    Cannonical LR parser - complete LR(1) parser
 
129
 
 
130
GLR (Generalized Left-to-right Rightmost derivation parser)
 
131
    is extension of an LR parser algorithm to handle nondeterministic and 
 
132
    ambiguous grammars.
 
133
    
 
134
LR(0) Parser
 
135
============
 
136
    LR(0), SLR, LALR parsers are implemented as finite automat
 
137
    
 
138
    Automat consists of 
 
139
        - Input buffer, example: 1+1$ ($ - is end of input)
 
140
        - Stack - stores list of states the automat has been in
 
141
        - Action Table - Gives a grammar rule to apply given the current state 
 
142
        and the current terminal in the input stream
 
143
            + depending on current state and current symbol in input buffer
 
144
            + possible actions
 
145
                *) shift to next element in input buffer, and change state
 
146
                to 'new_state'
 
147
                *) perform reduction rule 'm'
 
148
                *) done
 
149
        - Goto Table - ndicates what the next state of the parser will be if 
 
150
        it has recognized a certain nonterminal.
 
151
            + depending on 'current state' and non-terminal symbol
 
152
            encountered in input.
 
153
        - See details in articles about LR(0) parsers.
 
154
        
 
155
        
 
156
    Notation
 
157
    --------
 
158
    - Point near of symbol (asterix here) denotes state of parser.
 
159
      'E -> E* + B' - parser has recognized a string corresponding with E on 
 
160
      the input stream and now expects to read a '+'.
 
161
      
 
 
b'\\ No newline at end of file'