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

Revision 137, 22.0 KB checked in by xi, 9 years ago (diff)

Refactor resolver.

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