source: pyyaml/trunk/lib/yaml/parser.py @ 136

Revision 136, 21.8 KB checked in by xi, 9 years ago (diff)

Major refactoring.

Line 
1
2# YAML can be parsed by an LL(1) parser!
3#
4# We use the following production rules:
5# stream            ::= STREAM-START implicit_document? explicit_document* STREAM-END
6# explicit_document ::= DIRECTIVE* DOCUMENT-START block_node? DOCUMENT-END?
7# implicit_document ::= block_node DOCUMENT-END?
8# block_node    ::= ALIAS | properties? block_content
9# flow_node     ::= ALIAS | properties? flow_content
10# properties    ::= TAG ANCHOR? | ANCHOR TAG?
11# block_content     ::= block_collection | flow_collection | SCALAR
12# flow_content      ::= flow_collection | SCALAR
13# block_collection  ::= block_sequence | block_mapping
14# block_sequence    ::= BLOCK-SEQUENCE-START (BLOCK-ENTRY block_node?)* BLOCK-END
15# block_mapping     ::= BLOCK-MAPPING_START ((KEY block_node_or_indentless_sequence?)? (VALUE block_node_or_indentless_sequence?)?)* BLOCK-END
16# block_node_or_indentless_sequence ::= ALIAS | properties? (block_content | indentless_block_sequence)
17# indentless_block_sequence         ::= (BLOCK-ENTRY block_node?)+
18# flow_collection   ::= flow_sequence | flow_mapping
19# flow_sequence     ::= FLOW-SEQUENCE-START (flow_sequence_entry FLOW-ENTRY)* flow_sequence_entry? FLOW-SEQUENCE-END
20# flow_mapping      ::= FLOW-MAPPING-START (flow_mapping_entry FLOW-ENTRY)* flow_mapping_entry? FLOW-MAPPING-END
21# flow_sequence_entry   ::= flow_node | KEY flow_node? (VALUE flow_node?)?
22# flow_mapping_entry    ::= flow_node | KEY flow_node? (VALUE flow_node?)?
23
24# TODO: support for BOM within a stream.
25# stream ::= (BOM? implicit_document)? (BOM? explicit_document)* STREAM-END
26
27# FIRST sets:
28# stream: { STREAM-START }
29# explicit_document: { DIRECTIVE DOCUMENT-START }
30# implicit_document: FIRST(block_node)
31# block_node: { ALIAS TAG ANCHOR SCALAR BLOCK-SEQUENCE-START BLOCK-MAPPING-START FLOW-SEQUENCE-START FLOW-MAPPING-START }
32# flow_node: { ALIAS ANCHOR TAG SCALAR FLOW-SEQUENCE-START FLOW-MAPPING-START }
33# block_content: { BLOCK-SEQUENCE-START BLOCK-MAPPING-START FLOW-SEQUENCE-START FLOW-MAPPING-START SCALAR }
34# flow_content: { FLOW-SEQUENCE-START FLOW-MAPPING-START SCALAR }
35# block_collection: { BLOCK-SEQUENCE-START BLOCK-MAPPING-START }
36# flow_collection: { FLOW-SEQUENCE-START FLOW-MAPPING-START }
37# block_sequence: { BLOCK-SEQUENCE-START }
38# block_mapping: { BLOCK-MAPPING-START }
39# block_node_or_indentless_sequence: { ALIAS ANCHOR TAG SCALAR BLOCK-SEQUENCE-START BLOCK-MAPPING-START FLOW-SEQUENCE-START FLOW-MAPPING-START BLOCK-ENTRY }
40# indentless_sequence: { ENTRY }
41# flow_collection: { FLOW-SEQUENCE-START FLOW-MAPPING-START }
42# flow_sequence: { FLOW-SEQUENCE-START }
43# flow_mapping: { FLOW-MAPPING-START }
44# flow_sequence_entry: { ALIAS ANCHOR TAG SCALAR FLOW-SEQUENCE-START FLOW-MAPPING-START KEY }
45# flow_mapping_entry: { ALIAS ANCHOR TAG SCALAR FLOW-SEQUENCE-START FLOW-MAPPING-START KEY }
46
47__all__ = ['Parser', 'ParserError']
48
49from error import MarkedYAMLError
50from tokens import *
51from events import *
52from scanner import *
53
54class ParserError(MarkedYAMLError):
55    pass
56
57class Parser:
58    # Since writing a recursive-descendant parser is a straightforward task, we
59    # do not give many comments here.
60    # Note that we use Python generators. If you rewrite the parser in another
61    # language, you may replace all 'yield'-s with event handler calls.
62
63    DEFAULT_TAGS = {
64        u'!':   u'!',
65        u'!!':  u'tag:yaml.org,2002:',
66    }
67
68    def __init__(self):
69        self.current_event = None
70        self.yaml_version = None
71        self.tag_handles = {}
72        self.event_generator = self.parse_stream()
73
74    def check_event(self, *choices):
75        # Check the type of the next event.
76        if self.current_event is None:
77            try:
78                self.current_event = self.event_generator.next()
79            except StopIteration:
80                pass
81        if self.current_event is not None:
82            if not choices:
83                return True
84            for choice in choices:
85                if isinstance(self.current_event, choice):
86                    return True
87        return False
88
89    def peek_event(self):
90        # Get the next event.
91        if self.current_event is None:
92            try:
93                self.current_event = self.event_generator.next()
94            except StopIteration:
95                pass
96        return self.current_event
97
98    def get_event(self):
99        # Get the next event.
100        if self.current_event is None:
101            try:
102                self.current_event = self.event_generator.next()
103            except StopIteration:
104                pass
105        value = self.current_event
106        self.current_event = None
107        return value
108
109    def __iter__(self):
110        # Iterator protocol.
111        return self.event_generator
112
113    def parse_stream(self):
114        # STREAM-START implicit_document? explicit_document* STREAM-END
115
116        # Parse start of stream.
117        token = self.get_token()
118        yield StreamStartEvent(token.start_mark, token.end_mark,
119                encoding=token.encoding)
120
121        # Parse implicit document.
122        if not self.check_token(DirectiveToken, DocumentStartToken,
123                StreamEndToken):
124            self.tag_handles = self.DEFAULT_TAGS
125            token = self.peek_token()
126            start_mark = end_mark = token.start_mark
127            yield DocumentStartEvent(start_mark, end_mark,
128                    explicit=False)
129            for event in self.parse_block_node():
130                yield event
131            token = self.peek_token()
132            start_mark = end_mark = token.start_mark
133            explicit = False
134            while self.check_token(DocumentEndToken):
135                token = self.get_token()
136                end_mark = token.end_mark
137                explicit = True
138            yield DocumentEndEvent(start_mark, end_mark,
139                    explicit=explicit)
140
141        # Parse explicit documents.
142        while not self.check_token(StreamEndToken):
143            token = self.peek_token()
144            start_mark = token.start_mark
145            version, tags = self.process_directives()
146            if not self.check_token(DocumentStartToken):
147                raise ParserError(None, None,
148                        "expected '<document start>', but found %r"
149                        % self.peek_token().id,
150                        self.peek_token().start_mark)
151            token = self.get_token()
152            end_mark = token.end_mark
153            yield DocumentStartEvent(start_mark, end_mark,
154                    explicit=True, version=version, tags=tags)
155            if self.check_token(DirectiveToken,
156                    DocumentStartToken, DocumentEndToken, StreamEndToken):
157                yield self.process_empty_scalar(token.end_mark)
158            else:
159                for event in self.parse_block_node():
160                    yield event
161            token = self.peek_token()
162            start_mark = end_mark = token.start_mark
163            explicit = False
164            while self.check_token(DocumentEndToken):
165                token = self.get_token()
166                end_mark = token.end_mark
167                explicit=True
168            yield DocumentEndEvent(start_mark, end_mark,
169                    explicit=explicit)
170
171        # Parse end of stream.
172        token = self.get_token()
173        yield StreamEndEvent(token.start_mark, token.end_mark)
174
175    def process_directives(self):
176        # DIRECTIVE*
177        self.yaml_version = None
178        self.tag_handles = {}
179        while self.check_token(DirectiveToken):
180            token = self.get_token()
181            if token.name == u'YAML':
182                if self.yaml_version is not None:
183                    raise ParserError(None, None,
184                            "found duplicate YAML directive", token.start_mark)
185                major, minor = token.value
186                if major != 1:
187                    raise ParserError(None, None,
188                            "found incompatible YAML document (version 1.* is required)",
189                            token.start_mark)
190                self.yaml_version = token.value
191            elif token.name == u'TAG':
192                handle, prefix = token.value
193                if handle in self.tag_handles:
194                    raise ParserError(None, None,
195                            "duplicate tag handle %r" % handle.encode('utf-8'),
196                            token.start_mark)
197                self.tag_handles[handle] = prefix
198        if self.tag_handles:
199            value = self.yaml_version, self.tag_handles.copy()
200        else:
201            value = self.yaml_version, None
202        for key in self.DEFAULT_TAGS:
203            if key not in self.tag_handles:
204                self.tag_handles[key] = self.DEFAULT_TAGS[key]
205        return value
206
207    def parse_block_node(self):
208        return self.parse_node(block=True)
209
210    def parse_flow_node(self):
211        return self.parse_node()
212
213    def parse_block_node_or_indentless_sequence(self):
214        return self.parse_node(block=True, indentless_sequence=True)
215
216    def parse_node(self, block=False, indentless_sequence=False):
217        # block_node    ::= ALIAS | properties? block_content
218        # flow_node     ::= ALIAS | properties? flow_content
219        # properties    ::= TAG ANCHOR? | ANCHOR TAG?
220        # block_content     ::= block_collection | flow_collection | SCALAR
221        # flow_content      ::= flow_collection | SCALAR
222        # block_collection  ::= block_sequence | block_mapping
223        # block_node_or_indentless_sequence ::= ALIAS | properties?
224        #                                       (block_content | indentless_block_sequence)
225        if self.check_token(AliasToken):
226            token = self.get_token()
227            yield AliasEvent(token.value, token.start_mark, token.end_mark)
228        else:
229            anchor = None
230            tag = None
231            start_mark = end_mark = tag_mark = None
232            if self.check_token(AnchorToken):
233                token = self.get_token()
234                start_mark = token.start_mark
235                end_mark = token.end_mark
236                anchor = token.value
237                if self.check_token(TagToken):
238                    token = self.get_token()
239                    tag_mark = token.start_mark
240                    end_mark = token.end_mark
241                    tag = token.value
242            elif self.check_token(TagToken):
243                token = self.get_token()
244                start_mark = tag_mark = token.start_mark
245                end_mark = token.end_mark
246                tag = token.value
247                if self.check_token(AnchorToken):
248                    token = self.get_token()
249                    end_mark = token.end_mark
250                    anchor = token.value
251            if tag is not None and tag != u'!':
252                handle, suffix = tag
253                if handle is not None:
254                    if handle not in self.tag_handles:
255                        raise ParserError("while parsing a node", start_mark,
256                                "found undefined tag handle %r" % handle.encode('utf-8'),
257                                tag_mark)
258                    tag = self.tag_handles[handle]+suffix
259                else:
260                    tag = suffix
261            #if tag == u'!':
262            #    raise ParserError("while parsing a node", start_mark,
263            #            "found non-specific tag '!'", tag_mark,
264            #            "Please check 'http://pyyaml.org/wiki/YAMLNonSpecificTag' and share your opinion.")
265            if start_mark is None:
266                start_mark = end_mark = self.peek_token().start_mark
267            event = None
268            collection_events = None
269            if indentless_sequence and self.check_token(BlockEntryToken):
270                end_mark = self.peek_token().end_mark
271                event = SequenceStartEvent(anchor, tag, start_mark, end_mark)
272                collection_events = self.parse_indentless_sequence()
273            else:
274                if self.check_token(ScalarToken):
275                    token = self.get_token()
276                    end_mark = token.end_mark
277                    implicit = ((tag is None or tag == u'!') and token.implicit)
278                    event = ScalarEvent(anchor, tag, implicit, token.value,
279                            start_mark, end_mark, style=token.style)
280                elif self.check_token(FlowSequenceStartToken):
281                    end_mark = self.peek_token().end_mark
282                    event = SequenceStartEvent(anchor, tag, start_mark, end_mark,
283                            flow_style=True)
284                    collection_events = self.parse_flow_sequence()
285                elif self.check_token(FlowMappingStartToken):
286                    end_mark = self.peek_token().end_mark
287                    event = MappingStartEvent(anchor, tag, start_mark, end_mark,
288                            flow_style=True)
289                    collection_events = self.parse_flow_mapping()
290                elif block and self.check_token(BlockSequenceStartToken):
291                    end_mark = self.peek_token().start_mark
292                    event = SequenceStartEvent(anchor, tag, start_mark, end_mark,
293                            flow_style=False)
294                    collection_events = self.parse_block_sequence()
295                elif block and self.check_token(BlockMappingStartToken):
296                    end_mark = self.peek_token().start_mark
297                    event = MappingStartEvent(anchor, tag, start_mark, end_mark,
298                            flow_style=False)
299                    collection_events = self.parse_block_mapping()
300                elif anchor is not None or tag is not None:
301                    # Empty scalars are allowed even if a tag or an anchor is
302                    # specified.
303                    implicit = (tag is None or tag == u'!')
304                    event = ScalarEvent(anchor, tag, implicit, u'',
305                            start_mark, end_mark)
306                else:
307                    if block:
308                        node = 'block'
309                    else:
310                        node = 'flow'
311                    token = self.peek_token()
312                    raise ParserError("while scanning a %s node" % node, start_mark,
313                            "expected the node content, but found %r" % token.id,
314                            token.start_mark)
315            yield event
316            if collection_events is not None:
317                for event in collection_events:
318                    yield event
319
320    def parse_block_sequence(self):
321        # BLOCK-SEQUENCE-START (BLOCK-ENTRY block_node?)* BLOCK-END
322        token = self.get_token()
323        start_mark = token.start_mark
324        while self.check_token(BlockEntryToken):
325            token = self.get_token()
326            if not self.check_token(BlockEntryToken, BlockEndToken):
327                for event in self.parse_block_node():
328                    yield event
329            else:
330                yield self.process_empty_scalar(token.end_mark)
331        if not self.check_token(BlockEndToken):
332            token = self.peek_token()
333            raise ParserError("while scanning a block collection", start_mark,
334                    "expected <block end>, but found %r" % token.id, token.start_mark)
335        token = self.get_token()
336        yield SequenceEndEvent(token.start_mark, token.end_mark)
337
338    def parse_indentless_sequence(self):
339        # (BLOCK-ENTRY block_node?)+
340        while self.check_token(BlockEntryToken):
341            token = self.get_token()
342            if not self.check_token(BlockEntryToken,
343                    KeyToken, ValueToken, BlockEndToken):
344                for event in self.parse_block_node():
345                    yield event
346            else:
347                yield self.process_empty_scalar(token.end_mark)
348        token = self.peek_token()
349        yield SequenceEndEvent(token.start_mark, token.start_mark)
350
351    def parse_block_mapping(self):
352        # BLOCK-MAPPING_START
353        #   ((KEY block_node_or_indentless_sequence?)?
354        #   (VALUE block_node_or_indentless_sequence?)?)*
355        # BLOCK-END
356        token = self.get_token()
357        start_mark = token.start_mark
358        while self.check_token(KeyToken, ValueToken):
359            if self.check_token(KeyToken):
360                token = self.get_token()
361                if not self.check_token(KeyToken, ValueToken, BlockEndToken):
362                    for event in self.parse_block_node_or_indentless_sequence():
363                        yield event
364                else:
365                    yield self.process_empty_scalar(token.end_mark)
366            if self.check_token(ValueToken):
367                token = self.get_token()
368                if not self.check_token(KeyToken, ValueToken, BlockEndToken):
369                    for event in self.parse_block_node_or_indentless_sequence():
370                        yield event
371                else:
372                    yield self.process_empty_scalar(token.end_mark)
373            else:
374                token = self.peek_token()
375                yield self.process_empty_scalar(token.start_mark)
376        if not self.check_token(BlockEndToken):
377            token = self.peek_token()
378            raise ParserError("while scanning a block mapping", start_mark,
379                    "expected <block end>, but found %r" % token.id, token.start_mark)
380        token = self.get_token()
381        yield MappingEndEvent(token.start_mark, token.end_mark)
382
383    def parse_flow_sequence(self):
384        # flow_sequence     ::= FLOW-SEQUENCE-START
385        #                       (flow_sequence_entry FLOW-ENTRY)*
386        #                       flow_sequence_entry?
387        #                       FLOW-SEQUENCE-END
388        # flow_sequence_entry   ::= flow_node | KEY flow_node? (VALUE flow_node?)?
389        #
390        # Note that while production rules for both flow_sequence_entry and
391        # flow_mapping_entry are equal, their interpretations are different.
392        # For `flow_sequence_entry`, the part `KEY flow_node? (VALUE flow_node?)?`
393        # generate an inline mapping (set syntax).
394        token = self.get_token()
395        start_mark = token.start_mark
396        while not self.check_token(FlowSequenceEndToken):
397            if self.check_token(KeyToken):
398                token = self.get_token()
399                yield MappingStartEvent(None, None, # u'!',
400                        token.start_mark, token.end_mark,
401                        flow_style=True)
402                if not self.check_token(ValueToken,
403                        FlowEntryToken, FlowSequenceEndToken):
404                    for event in self.parse_flow_node():
405                        yield event
406                else:
407                    yield self.process_empty_scalar(token.end_mark)
408                if self.check_token(ValueToken):
409                    token = self.get_token()
410                    if not self.check_token(FlowEntryToken, FlowSequenceEndToken):
411                        for event in self.parse_flow_node():
412                            yield event
413                    else:
414                        yield self.process_empty_scalar(token.end_mark)
415                else:
416                    token = self.peek_token()
417                    yield self.process_empty_scalar(token.start_mark)
418                token = self.peek_token()
419                yield MappingEndEvent(token.start_mark, token.start_mark)
420            else:
421                for event in self.parse_flow_node():
422                    yield event
423            if not self.check_token(FlowEntryToken, FlowSequenceEndToken):
424                token = self.peek_token()
425                raise ParserError("while scanning a flow sequence", start_mark,
426                        "expected ',' or ']', but got %r" % token.id, token.start_mark)
427            if self.check_token(FlowEntryToken):
428                self.get_token()
429        token = self.get_token()
430        yield SequenceEndEvent(token.start_mark, token.end_mark)
431
432    def parse_flow_mapping(self):
433        # flow_mapping      ::= FLOW-MAPPING-START
434        #                       (flow_mapping_entry FLOW-ENTRY)*
435        #                       flow_mapping_entry?
436        #                       FLOW-MAPPING-END
437        # flow_mapping_entry    ::= flow_node | KEY flow_node? (VALUE flow_node?)?
438        token = self.get_token()
439        start_mark = token.start_mark
440        while not self.check_token(FlowMappingEndToken):
441            if self.check_token(KeyToken):
442                token = self.get_token()
443                if not self.check_token(ValueToken,
444                        FlowEntryToken, FlowMappingEndToken):
445                    for event in self.parse_flow_node():
446                        yield event
447                else:
448                    yield self.process_empty_scalar(token.end_mark)
449                if self.check_token(ValueToken):
450                    token = self.get_token()
451                    if not self.check_token(FlowEntryToken, FlowMappingEndToken):
452                        for event in self.parse_flow_node():
453                            yield event
454                    else:
455                        yield self.process_empty_scalar(token.end_mark)
456                else:
457                    token = self.peek_token()
458                    yield self.process_empty_scalar(token.start_mark)
459            else:
460                for event in self.parse_flow_node():
461                    yield event
462                yield self.process_empty_scalar(self.peek_token().start_mark)
463            if not self.check_token(FlowEntryToken, FlowMappingEndToken):
464                token = self.peek_token()
465                raise ParserError("while scanning a flow mapping", start_mark,
466                        "expected ',' or '}', but got %r" % token.id, token.start_mark)
467            if self.check_token(FlowEntryToken):
468                self.get_token()
469        if not self.check_token(FlowMappingEndToken):
470            token = self.peek_token()
471            raise ParserError("while scanning a flow mapping", start_mark,
472                    "expected '}', but found %r" % token.id, token.start_mark)
473        token = self.get_token()
474        yield MappingEndEvent(token.start_mark, token.end_mark)
475
476    def process_empty_scalar(self, mark):
477        return ScalarEvent(None, None, True, u'', mark, mark)
478
Note: See TracBrowser for help on using the repository browser.