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

Revision 132, 22.3 KB checked in by xi, 9 years ago (diff)

Emitter is done!!!

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