Revision: 17990
Author: [email protected]
Date: Fri Nov 22 08:40:59 2013 UTC
Log: Experimental parser: KeyEncoding class added
[email protected]
BUG=
Review URL: https://codereview.chromium.org/82983002
http://code.google.com/p/v8/source/detail?r=17990
Modified:
/branches/experimental/parser/tools/lexer_generator/automaton.py
/branches/experimental/parser/tools/lexer_generator/code_generator.py
/branches/experimental/parser/tools/lexer_generator/code_generator_test.py
/branches/experimental/parser/tools/lexer_generator/dfa.py
/branches/experimental/parser/tools/lexer_generator/generator.py
/branches/experimental/parser/tools/lexer_generator/lexer_test.py
/branches/experimental/parser/tools/lexer_generator/nfa.py
/branches/experimental/parser/tools/lexer_generator/nfa_builder.py
/branches/experimental/parser/tools/lexer_generator/rule_parser.py
/branches/experimental/parser/tools/lexer_generator/rule_parser_test.py
/branches/experimental/parser/tools/lexer_generator/transition_key_test.py
/branches/experimental/parser/tools/lexer_generator/transition_keys.py
=======================================
--- /branches/experimental/parser/tools/lexer_generator/automaton.py Wed
Nov 20 10:06:26 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/automaton.py Fri
Nov 22 08:40:59 2013 UTC
@@ -132,6 +132,12 @@
class Automaton(object):
+ def __init__(self, encoding):
+ self.__encoding = encoding
+
+ def encoding(self):
+ return self.__encoding
+
@staticmethod
def visit_states(edge, visitor, visit_state = None, state_iter = None):
if not state_iter:
=======================================
--- /branches/experimental/parser/tools/lexer_generator/code_generator.py
Thu Nov 21 12:47:51 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/code_generator.py
Fri Nov 22 08:40:59 2013 UTC
@@ -35,7 +35,6 @@
def __init__(self,
rule_processor,
- encoding = 'latin1',
minimize_default = True,
inline = True,
switching = True,
@@ -52,7 +51,6 @@
self.__log = log
self.__inline = inline
self.__switching = switching
- self.__encoding = encoding
def __state_cmp(self, left, right):
if left['original_node_number'] == self.__start_node_number:
@@ -96,7 +94,7 @@
return cmp(left[1], right[1])
@staticmethod
- def __transform_state(state):
+ def __transform_state(encoding, state):
# action data
action = state.action()
entry_action = None if not action else action.entry_action()
@@ -110,7 +108,7 @@
# map transition keys to disjoint ranges
disjoint_keys = {'value' : []}
def f((key, state)):
- ranges = list(key.range_iter())
+ ranges = list(key.range_iter(encoding))
disjoint_keys['value'] += ranges
return (ranges, state)
transitions = map(f, transitions)
@@ -203,7 +201,9 @@
def __canonicalize_traversal(self):
dfa_states = []
self.__dfa.visit_all_states(lambda state, acc:
dfa_states.append(state))
- dfa_states = map(CodeGenerator.__transform_state, dfa_states)
+ encoding = self.__dfa.encoding()
+ f = lambda state : CodeGenerator.__transform_state(encoding, state)
+ dfa_states = map(f, dfa_states)
id_map = {x['original_node_number'] : x for x in dfa_states}
CodeGenerator.__compute_depths(self.__start_node_number, 1, id_map)
dfa_states = sorted(dfa_states, cmp=self.__state_cmp)
@@ -246,9 +246,10 @@
undefined = jinja2.StrictUndefined)
template = template_env.get_template('code_generator.jinja')
- if self.__encoding == 'latin1':
+ encoding = self.__dfa.encoding().name()
+ if encoding == 'latin1':
char_type = 'uint8_t'
- elif self.__encoding == 'utf16':
+ elif encoding == 'utf16':
char_type = 'uint16_t'
else:
raise Exception('Unsupported encoding %s' % encoding)
@@ -257,5 +258,5 @@
debug_print = self.__debug_print,
default_action = default_action,
dfa_states = dfa_states,
- encoding = self.__encoding,
+ encoding = encoding,
char_type = char_type)
=======================================
---
/branches/experimental/parser/tools/lexer_generator/code_generator_test.py
Tue Nov 19 12:28:18 2013 UTC
+++
/branches/experimental/parser/tools/lexer_generator/code_generator_test.py
Fri Nov 22 08:40:59 2013 UTC
@@ -41,4 +41,4 @@
"foo" <|{FOO}|>
eos <|terminate|>
default_action <{DEFAULT}>'''
- CodeGenerator(RuleProcessor.parse(rules))
+ CodeGenerator(RuleProcessor.parse(rules, 'latin1'))
=======================================
--- /branches/experimental/parser/tools/lexer_generator/dfa.py Wed Nov 20
10:42:41 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/dfa.py Fri Nov 22
08:40:59 2013 UTC
@@ -78,8 +78,8 @@
class Dfa(Automaton):
- def __init__(self, start_name, mapping):
- super(Dfa, self).__init__()
+ def __init__(self, encoding, start_name, mapping):
+ super(Dfa, self).__init__(encoding)
self.__terminal_set = set()
name_map = {}
for name, node_data in mapping.items():
@@ -95,7 +95,7 @@
inversion[state] = []
inversion[state].append(key)
for state, keys in inversion.items():
- merged_key = TransitionKey.merged_key(keys)
+ merged_key = TransitionKey.merged_key(encoding, keys)
node.add_transition(merged_key, name_map[state])
self.__start = name_map[start_name]
self.__node_count = len(mapping)
@@ -223,7 +223,9 @@
# TransitionKey [c-h], S1 and S3 cannot be in the same partition. This
will
# become clear when we check the transition for TransitionKey [c-d]
(S1 has
# a transition to S2, S3 has a transition to S4).
- self.__alphabet = list(TransitionKey.disjoint_keys(chain(*all_keys)))
+ encoding = self.__dfa.encoding()
+ self.__alphabet = list(
+ TransitionKey.disjoint_keys(encoding, chain(*all_keys)))
# For each state and each TransitionKey in the alphabet, find out which
# transition we take from the state with the TransitionKey.
@@ -388,4 +390,4 @@
if new_partitions:
partitions |= new_partitions
(start_name, mapping) =
self.__create_states_from_partitions(partitions)
- return Dfa(start_name, mapping)
+ return Dfa(self.__dfa.encoding(), start_name, mapping)
=======================================
--- /branches/experimental/parser/tools/lexer_generator/generator.py Wed
Nov 20 16:10:09 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/generator.py Fri
Nov 22 08:40:59 2013 UTC
@@ -112,7 +112,7 @@
if verbose:
print "parsing %s" % re_file
with open(re_file, 'r') as f:
- rule_processor = RuleProcessor.parse(f.read())
+ rule_processor = RuleProcessor.parse(f.read(), args.encoding)
if minimize_default:
if args.no_verify_default:
@@ -135,7 +135,6 @@
code_file = args.code
if code_file:
code_generator = CodeGenerator(rule_processor,
- encoding = args.encoding,
minimize_default = minimize_default,
log = verbose,
inline = not args.no_inline,
=======================================
--- /branches/experimental/parser/tools/lexer_generator/lexer_test.py Wed
Nov 20 10:06:26 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/lexer_test.py Fri
Nov 22 08:40:59 2013 UTC
@@ -33,7 +33,7 @@
def __verify_action_stream(self, rules, string, expected):
expected = map(lambda (action, s) : (Action(None, (action, None)), s),
expected)
- automata = RuleProcessor.parse(rules).default_automata()
+ automata = RuleProcessor.parse(rules, 'latin1').default_automata()
for automaton in [automata.nfa(), automata.dfa(),
automata.minimal_dfa()]:
for i, (action, start, stop) in enumerate(automaton.lex(string)):
self.assertEquals(expected[i][0], action)
=======================================
--- /branches/experimental/parser/tools/lexer_generator/nfa.py Wed Nov 20
10:53:56 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/nfa.py Fri Nov 22
08:40:59 2013 UTC
@@ -106,8 +106,8 @@
class Nfa(Automaton):
- def __init__(self, start, end, nodes_created):
- super(Nfa, self).__init__()
+ def __init__(self, encoding, start, end, nodes_created):
+ super(Nfa, self).__init__(encoding)
self.__start = start
self.__end = end
self.__verify(nodes_created)
@@ -126,13 +126,12 @@
assert count == nodes_created
@staticmethod
- def __gather_transition_keys(state_set):
+ def __gather_transition_keys(encoding, state_set):
keys = set(chain(*map(lambda state: state.key_iter(), state_set)))
keys.discard(TransitionKey.epsilon())
- return TransitionKey.disjoint_keys(keys)
+ return TransitionKey.disjoint_keys(encoding, keys)
- @staticmethod
- def __to_dfa(nfa_state_set, dfa_nodes, end_node):
+ def __to_dfa(self, nfa_state_set, dfa_nodes, end_node):
nfa_state_set = Automaton.epsilon_closure(nfa_state_set)
assert nfa_state_set
name = ".".join(str(x.node_number()) for x in sorted(nfa_state_set))
@@ -142,11 +141,11 @@
'transitions': {},
'terminal': end_node in nfa_state_set,
'action' : Action.dominant_action(nfa_state_set)}
- for key in Nfa.__gather_transition_keys(nfa_state_set):
+ for key in Nfa.__gather_transition_keys(self.encoding(),
nfa_state_set):
match_states = set()
f = lambda state: state.transition_state_iter_for_key(key)
match_states |= set(chain(*map(f, nfa_state_set)))
- transition_state = Nfa.__to_dfa(match_states, dfa_nodes, end_node)
+ transition_state = self.__to_dfa(match_states, dfa_nodes, end_node)
dfa_nodes[name]['transitions'][key] = transition_state
return name
=======================================
--- /branches/experimental/parser/tools/lexer_generator/nfa_builder.py Wed
Nov 20 10:53:56 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/nfa_builder.py Fri
Nov 22 08:40:59 2013 UTC
@@ -31,16 +31,14 @@
class NfaBuilder(object):
- def __init__(self):
+ def __init__(self, encoding, character_classes = {}):
self.__node_number = 0
self.__operation_map = {}
self.__members = getmembers(self)
- self.__character_classes = {}
+ self.__encoding = encoding
+ self.__character_classes = character_classes
self.__states = []
- def set_character_classes(self, classes):
- self.__character_classes = classes
-
def __new_state(self):
self.__node_number += 1
return NfaState()
@@ -107,18 +105,19 @@
return (state, [state])
def __literal(self, graph):
- return self.__key_state(TransitionKey.single_char(graph[1]))
+ return self.__key_state(
+ TransitionKey.single_char(self.__encoding, graph[1]))
def __class(self, graph):
- return self.__key_state(
- TransitionKey.character_class(graph, self.__character_classes))
+ return self.__key_state(TransitionKey.character_class(
+ self.__encoding, graph, self.__character_classes))
def __not_class(self, graph):
- return self.__key_state(
- TransitionKey.character_class(graph, self.__character_classes))
+ return self.__key_state(TransitionKey.character_class(
+ self.__encoding, graph, self.__character_classes))
def __any(self, graph):
- return self.__key_state(TransitionKey.any())
+ return self.__key_state(TransitionKey.any(self.__encoding))
def __epsilon(self, graph):
start = self.__new_state()
@@ -216,7 +215,7 @@
Automaton.visit_states(set([start_state]), outer)
@staticmethod
- def __replace_catch_all(state):
+ def __replace_catch_all(encoding, state):
catch_all = TransitionKey.unique('catch_all')
transitions = state.transitions()
if not catch_all in transitions:
@@ -227,7 +226,7 @@
keys = reduce(f, reachable_states, set())
keys.discard(TransitionKey.epsilon())
keys.discard(catch_all)
- inverse_key = TransitionKey.inverse_key(keys)
+ inverse_key = TransitionKey.inverse_key(encoding, keys)
if inverse_key:
transitions[inverse_key] = transitions[catch_all]
del transitions[catch_all]
@@ -236,9 +235,9 @@
(start, end, nodes_created) = self.__nfa(graph)
end.close(None)
self.__compute_epsilon_closures(start)
- f = lambda node, state: self.__replace_catch_all(node)
+ f = lambda node, state: self.__replace_catch_all(self.__encoding, node)
Automaton.visit_states(set([start]), f)
- return Nfa(start, end, nodes_created)
+ return Nfa(self.__encoding, start, end, nodes_created)
@staticmethod
def add_action(graph, action):
=======================================
--- /branches/experimental/parser/tools/lexer_generator/rule_parser.py Thu
Nov 21 17:52:02 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/rule_parser.py Fri
Nov 22 08:40:59 2013 UTC
@@ -31,16 +31,17 @@
from regex_parser import RegexParser
from nfa_builder import NfaBuilder
from dfa import Dfa
-from transition_keys import TransitionKey
+from transition_keys import TransitionKey, KeyEncoding
class RuleParserState:
- def __init__(self):
+ def __init__(self, encoding):
self.aliases = {}
self.character_classes = {}
self.current_state = None
self.rules = {}
self.transitions = set()
+ self.encoding = encoding
def parse(self, string):
return RuleParser.parse(string, self)
@@ -70,7 +71,8 @@
if graph[0] == 'CLASS' or graph[0] == 'NOT_CLASS':
classes = state.character_classes
assert not p[1] in classes
- classes[p[1]] = TransitionKey.character_class(graph, classes)
+ encoding = state.encoding
+ classes[p[1]] = TransitionKey.character_class(encoding, graph,
classes)
def p_rules(self, p):
'''rules : state_change transition_rules rules
@@ -260,8 +262,8 @@
self.__process_parser_state(parser_state)
@staticmethod
- def parse(string):
- parser_state = RuleParserState()
+ def parse(string, encoding_name):
+ parser_state = RuleParserState(KeyEncoding.get(encoding_name))
RuleParser.parse(string, parser_state)
return RuleProcessor(parser_state)
@@ -288,7 +290,7 @@
def dfa(self):
if not self.__dfa:
(start, dfa_nodes) = self.nfa().compute_dfa()
- self.__dfa = Dfa(start, dfa_nodes)
+ self.__dfa = Dfa(self.nfa().encoding(), start, dfa_nodes)
return self.__dfa
def minimal_dfa(self):
@@ -298,8 +300,7 @@
def __process_parser_state(self, parser_state):
rule_map = {}
- builder = NfaBuilder()
- builder.set_character_classes(parser_state.character_classes)
+ builder = NfaBuilder(parser_state.encoding,
parser_state.character_classes)
assert 'default' in parser_state.rules
def process(subgraph, v):
graphs = []
=======================================
--- /branches/experimental/parser/tools/lexer_generator/rule_parser_test.py
Thu Nov 14 20:25:22 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/rule_parser_test.py
Fri Nov 22 08:40:59 2013 UTC
@@ -26,13 +26,14 @@
# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
import unittest
+from transition_keys import KeyEncoding
from rule_parser import RuleParserState
from regex_parser import RegexParser
class RuleParserTestCase(unittest.TestCase):
def setUp(self):
- self.state = RuleParserState()
+ self.state = RuleParserState(KeyEncoding.get('latin1'))
def parse(self, string):
return self.state.parse(string)
=======================================
---
/branches/experimental/parser/tools/lexer_generator/transition_key_test.py
Wed Nov 20 16:10:09 2013 UTC
+++
/branches/experimental/parser/tools/lexer_generator/transition_key_test.py
Fri Nov 22 08:40:59 2013 UTC
@@ -26,15 +26,18 @@
# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
import unittest
-from transition_keys import TransitionKey
+from transition_keys import TransitionKey, KeyEncoding
from regex_parser import RegexParser
class TransitionKeyTestCase(unittest.TestCase):
+ __encoding = KeyEncoding.get('latin1')
+
__equal_pairs = [
(TransitionKey.epsilon(), TransitionKey.epsilon()),
- (TransitionKey.any(), TransitionKey.any()),
- (TransitionKey.single_char('a'), TransitionKey.single_char('a')),
+ (TransitionKey.any(__encoding), TransitionKey.any(__encoding)),
+ (TransitionKey.single_char(__encoding, 'a'),
+ TransitionKey.single_char(__encoding, 'a')),
]
def test_eq(self):
@@ -54,6 +57,7 @@
("a-z:whitespace::letter:" , "abc" , "123"),
]
classes = {}
+ encoding = self.__encoding
for (string, match, no_match) in data:
for invert in [False, True]:
if invert:
@@ -64,25 +68,26 @@
token = "CLASS"
graph = RegexParser.parse(regex)
assert graph[0] == token
- key = TransitionKey.character_class(graph, classes)
+ key = TransitionKey.character_class(encoding, graph, classes)
for c in match:
self.assertEqual(invert, not key.matches_char(c))
for c in no_match:
self.assertEqual(invert, key.matches_char(c))
def test_self_defined_classes(self):
+ encoding = self.__encoding
graph = RegexParser.parse("[a-z]")
classes = {
- 'self_defined' : TransitionKey.character_class(graph, {})}
+ 'self_defined' : TransitionKey.character_class(encoding, graph, {})}
graph = RegexParser.parse("[^:self_defined:]")
- key = TransitionKey.character_class(graph, classes)
+ key = TransitionKey.character_class(encoding, graph, classes)
self.assertTrue(key.matches_char('A'))
-
def test_disjoint_keys(self):
- key1 = TransitionKey([(1, 10)])
- key2 = TransitionKey([(5, 15)])
- disjoint_set = TransitionKey.disjoint_keys(set([key1, key2]))
- self.assertTrue(TransitionKey([(1, 4)]) in disjoint_set)
- self.assertTrue(TransitionKey([(5, 10)]) in disjoint_set)
- self.assertTrue(TransitionKey([(11, 15)]) in disjoint_set)
+ encoding = self.__encoding
+ key1 = TransitionKey(encoding, [(1, 10)])
+ key2 = TransitionKey(encoding, [(5, 15)])
+ disjoint_set = TransitionKey.disjoint_keys(encoding, set([key1, key2]))
+ self.assertTrue(TransitionKey(encoding, [(1, 4)]) in disjoint_set)
+ self.assertTrue(TransitionKey(encoding, [(5, 10)]) in disjoint_set)
+ self.assertTrue(TransitionKey(encoding, [(11, 15)]) in disjoint_set)
=======================================
--- /branches/experimental/parser/tools/lexer_generator/transition_keys.py
Thu Nov 21 12:47:51 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/transition_keys.py
Fri Nov 22 08:40:59 2013 UTC
@@ -25,9 +25,78 @@
# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+from types import TupleType
from string import printable
-class TransitionKey:
+class KeyEncoding(object):
+
+ __encodings = {}
+
+ @staticmethod
+ def get(name):
+ if not KeyEncoding.__encodings:
+ Latin1Encoding()
+ Utf16Encoding()
+ return KeyEncoding.__encodings[name]
+
+ def __init__(self, name, primary_range, class_names):
+ assert not name in KeyEncoding.__encodings
+ KeyEncoding.__encodings[name] = self
+ assert primary_range[0] <= primary_range[1]
+ assert primary_range[0] >= 0
+ self.__name = name
+ self.__primary_range = primary_range
+ self.__lower_bound = primary_range[0]
+ self.__upper_bound = primary_range[1] + len(class_names)
+ f = lambda i : (i + primary_range[1] + 1, i + primary_range[1] + 1)
+ self.__class_ranges = {name : f(i) for i, name in
enumerate(class_names)}
+ self.__predefined_ranges = {}
+
+ def name(self):
+ return self.__name
+
+ def add_predefined_range(self, name, ranges):
+ # TODO verify disjointness
+ self.__predefined_ranges[name] = ranges
+
+ def lower_bound(self):
+ return self.__lower_bound
+
+ def upper_bound(self):
+ return self.__upper_bound
+
+ def primary_range(self):
+ return self.__primary_range
+
+ def class_range(self, name):
+ ranges = self.__class_ranges
+ return None if not name in ranges else ranges[name]
+
+ def class_range_iter(self):
+ return self.__class_ranges.iteritems()
+
+ def class_value_iter(self):
+ return self.__class_ranges.itervalues()
+
+ def predefined_range_iter(self, name):
+ ranges = self.__predefined_ranges
+ return None if not name in ranges else iter(ranges[name])
+
+ def is_primary_range(self, r):
+ assert self.lower_bound() <= r[0] and r[1] <= self.upper_bound()
+ primary_range = self.__primary_range
+ if (primary_range[0] <= r[0] and r[1] <= primary_range[1]):
+ return True
+ assert r[0] == r[1]
+ return False
+
+ def in_primary_range(self, c):
+ return self.is_primary_range((c, c))
+
+ def is_class_range(self, r):
+ return not self.is_primary_range(r)
+
+class TransitionKey(object):
'''Represents a transition from a state in DFA or NFA to another state.
A transition key has a list of character ranges and a list of class
ranges
@@ -36,103 +105,67 @@
ranges generate simple checks and the class ranges generate more
complicated
conditions, e.g., function calls.'''
- __class_bounds = {
- 'latin_1' : (1, 255),
- # These are not real ranges; they just need to be separate from any
real
- # ranges.
- 'non_latin_1_whitespace' : (256, 256),
- 'non_latin_1_letter' : (257, 257),
- 'non_latin_1_identifier_part_not_letter' : (258, 258),
- 'non_latin_1_line_terminator' : (259, 259),
- 'eos' : (260, 260),
- 'zero' : (261, 261),
- 'byte_order_mark' : (262, 262),
- 'non_latin_1_everything_else' : (263, 263),
+ __cached_keys = {
+ 'no_encoding' : {},
+ 'latin1' : {},
+ 'utf8' : {},
+ 'utf16' : {},
}
- __lower_bound = min(__class_bounds.values(), key=lambda item: item[0])[0]
- __upper_bound = max(__class_bounds.values(), key=lambda item: item[1])[1]
-
- __cached_keys = {}
__unique_key_counter = -1
- __predefined_ranges = {
- 'whitespace' : [
- (9, 9), (11, 12), (32, 32), (133, 133), (160, 160),
- __class_bounds['non_latin_1_whitespace']],
- 'letter' : [
- (65, 90), (97, 122), (170, 170), (181, 181),
- (186, 186), (192, 214), (216, 246), (248, 255),
- __class_bounds['non_latin_1_letter']],
- 'line_terminator' : [
- (10, 10), (13, 13),
- __class_bounds['non_latin_1_line_terminator']],
- 'identifier_part_not_letter' : [
- (48, 57), (95, 95),
- __class_bounds['non_latin_1_identifier_part_not_letter']],
- }
-
- @staticmethod
- def __in_latin_1(char):
- bound = TransitionKey.__class_bounds['latin_1']
- return (bound[0] <= char and char <= bound[1])
-
- @staticmethod
- def __is_class_range(r):
- return r[0] == r[1] and not TransitionKey.__in_latin_1(r[0])
-
@staticmethod
def __is_unique_range(r):
- return r[0] == r[1] and r[0] < TransitionKey.__lower_bound
+ return (r[0] == r[1] and
+ r[0] < 0 and
+ r[1] > TransitionKey.__unique_key_counter)
@staticmethod
- def __verify_ranges(ranges, check_merged):
+ def __verify_ranges(encoding, ranges, check_merged):
assert ranges
- if len(ranges) == 1 and TransitionKey.__is_class_range(ranges[0]):
+ if len(ranges) == 1 and TransitionKey.__is_unique_range(ranges[0]):
return
last = None
for r in ranges:
- assert TransitionKey.__lower_bound <= r[0]
- assert r[1] <= TransitionKey.__upper_bound
- assert r[0] <= r[1]
- r_is_class = TransitionKey.__is_class_range(r)
+ assert not TransitionKey.__is_unique_range(r)
+ r_is_class = encoding.is_class_range(r)
# Assert that the ranges are in order.
if last != None and check_merged:
assert last[1] + 1 < r[0] or r_is_class
- if not TransitionKey.__in_latin_1(r[0]):
- assert r_is_class
- if not TransitionKey.__in_latin_1(r[1]):
- assert r_is_class
last = r
def __is_unique(self):
return len(self.__ranges) == 1 and
self.__is_unique_range(self.__ranges[0])
@staticmethod
- def __cached_key(name, bounds_getter):
- if not name in TransitionKey.__cached_keys:
+ def __cached_key(encoding, name, bounds_getter):
+ encoding_name = encoding.name() if encoding else 'no_encoding'
+ cache = TransitionKey.__cached_keys[encoding_name]
+ if not name in cache:
bounds = bounds_getter(name)
- TransitionKey.__cached_keys[name] = TransitionKey(bounds, name)
- return TransitionKey.__cached_keys[name]
+ cache[name] = TransitionKey(encoding, bounds, name)
+ return cache[name]
@staticmethod
def epsilon():
'''Returns a TransitionKey for the epsilon (empty) transition.'''
- return TransitionKey.__cached_key('epsilon', lambda name : [])
+ return TransitionKey.__cached_key(None, 'epsilon', lambda name : [])
@staticmethod
- def any():
+ def any(encoding):
'''Returns a TransitionKey which matches any character.'''
return TransitionKey.__cached_key(
+ encoding,
'any',
- lambda name : sorted(TransitionKey.__class_bounds.values()))
+ lambda name : sorted(
+ list(encoding.class_value_iter()) +
[encoding.primary_range()]))
@staticmethod
- def single_char(char):
+ def single_char(encoding, char):
'''Returns a TransitionKey for a single-character transition.'''
- char = ord(char)
- assert TransitionKey.__in_latin_1(char)
- return TransitionKey([(char, char)])
+ r = (ord(char), ord(char))
+ assert encoding.is_primary_range(r)
+ return TransitionKey(encoding, [r])
@staticmethod
def unique(name):
@@ -145,10 +178,10 @@
TransitionKey.__unique_key_counter -= 1
return [(bound, bound)]
name = '__' + name
- return TransitionKey.__cached_key(name, get_bounds)
+ return TransitionKey.__cached_key(None, name, get_bounds)
@staticmethod
- def __process_graph(graph, ranges, key_map):
+ def __process_graph(encoding, graph, ranges, key_map):
key = graph[0]
if key == 'RANGE':
ranges.append((ord(graph[1]), ord(graph[2])))
@@ -156,19 +189,19 @@
ranges.append((ord(graph[1]), ord(graph[1])))
elif key == 'CAT':
for x in [graph[1], graph[2]]:
- TransitionKey.__process_graph(x, ranges, key_map)
+ TransitionKey.__process_graph(encoding, x, ranges, key_map)
elif key == 'CHARACTER_CLASS':
class_name = graph[1]
- if class_name in TransitionKey.__class_bounds:
+ if encoding.class_range(class_name):
+ r = encoding.class_range(class_name)
if class_name in key_map:
- assert (key_map[class_name] ==
- TransitionKey([TransitionKey.__class_bounds[class_name]]))
- ranges.append(TransitionKey.__class_bounds[class_name])
- elif class_name in TransitionKey.__predefined_ranges:
+ assert key_map[class_name] == TransitionKey(encoding, [r])
+ ranges.append(r)
+ elif encoding.predefined_range_iter(class_name):
+ rs = list(encoding.predefined_range_iter(class_name))
if class_name in key_map:
- assert (key_map[class_name] ==
- TransitionKey(TransitionKey.__predefined_ranges[class_name]))
- ranges += TransitionKey.__predefined_ranges[class_name]
+ assert key_map[class_name] == TransitionKey(encoding, rs)
+ ranges += rs
elif class_name in key_map:
ranges += key_map[class_name].__ranges
else:
@@ -177,7 +210,7 @@
raise Exception('bad key [%s]' % key)
@staticmethod
- def character_class(graph, key_map):
+ def character_class(encoding, graph, key_map):
'''Processes 'graph' (a representation of a character class in the rule
file), and constructs a TransitionKey based on it. 'key_map' contains
already constructed aliases for character classes (they can be used in
the
@@ -188,12 +221,12 @@
ranges = []
assert graph[0] == 'CLASS' or graph[0] == 'NOT_CLASS'
invert = graph[0] == 'NOT_CLASS'
- TransitionKey.__process_graph(graph[1], ranges, key_map)
- return TransitionKey.__key_from_ranges(invert, ranges)
+ TransitionKey.__process_graph(encoding, graph[1], ranges, key_map)
+ return TransitionKey.__key_from_ranges(encoding, invert, ranges)
def matches_char(self, char):
char = ord(char)
- # TODO class checks
+ assert char < 128
for r in self.__ranges:
if r[0] <= char and char <= r[1]: return True
return False
@@ -233,25 +266,23 @@
def __hash__(self):
if self.__cached_hash == None:
- initial_hash = hash((-1, TransitionKey.__upper_bound + 1))
- f = lambda acc, r: acc ^ hash(r)
- self.__cached_hash = reduce(f, self.__ranges, initial_hash)
+ self.__cached_hash = hash(self.__ranges)
return self.__cached_hash
def __eq__(self, other):
return isinstance(other, self.__class__) and self.__ranges ==
other.__ranges
@staticmethod
- def __class_name(r):
- for name, v in TransitionKey.__class_bounds.items():
+ def __class_name(encoding, r):
+ for name, v in encoding.class_range_iter():
if r == v: return name
assert False
- def range_iter(self):
+ def range_iter(self, encoding):
assert not self == TransitionKey.epsilon() and not self.__is_unique()
for r in self.__ranges:
- if self.__is_class_range(r):
- yield ('CLASS', TransitionKey.__class_name(r))
+ if encoding.is_class_range(r):
+ yield ('CLASS', TransitionKey.__class_name(encoding, r))
else:
yield ('LATIN_1', r)
@@ -262,11 +293,13 @@
}
@staticmethod
- def __range_str(r):
- if TransitionKey.__is_class_range(r):
- return TransitionKey.__class_name(r)
+ def __range_str(encoding, r):
+ if encoding and encoding.is_class_range(r):
+ return TransitionKey.__class_name(encoding, r)
def to_str(x):
- assert TransitionKey.__in_latin_1(x)
+ assert not encoding or encoding.in_primary_range(x)
+ if x > 127:
+ return str(x)
if not x in TransitionKey.__printable_cache:
res = "'%s'" % chr(x) if chr(x) in printable else str(x)
TransitionKey.__printable_cache[x] = res
@@ -276,30 +309,34 @@
else:
return '[%s-%s]' % (to_str(r[0]), to_str(r[1]))
- def __init__(self, ranges, name = None):
+ def __init__(self, encoding, ranges, name = None):
if not ranges:
assert name == 'epsilon'
- assert not name in TransitionKey.__cached_keys
+ assert not name in TransitionKey.__cached_keys['no_encoding']
else:
- TransitionKey.__verify_ranges(ranges, True)
+ TransitionKey.__verify_ranges(encoding, ranges, True)
self.__name = name
self.__ranges = tuple(ranges) # immutable
self.__cached_hash = None
- def __str__(self):
+ def to_string(self, encoding):
if self.__name:
return self.__name
- return ', '.join(TransitionKey.__range_str(x) for x in self.__ranges)
+ strings = [TransitionKey.__range_str(encoding, x) for x in
self.__ranges]
+ return ', '.join(strings)
+
+ def __str__(self):
+ self.to_string(None)
@staticmethod
- def __disjoint_keys(range_map):
+ def __disjoint_keys(encoding, range_map):
'''Takes a set of possibly overlapping ranges, returns a list of ranges
which don't overlap and which cover the same points as the original
set. range_map is a map from lower bounds to a list of upper bounds.'''
sort = lambda x : sorted(set(x))
range_map = sorted(map(lambda (k, v): (k, sort(v)), range_map.items()))
ranges = []
- upper_bound = TransitionKey.__upper_bound + 1
+ upper_bound = encoding.upper_bound() + 1
for i in range(len(range_map)):
(left, left_values) = range_map[i]
next = range_map[i + 1][0] if i != len(range_map) - 1 else
upper_bound
@@ -319,23 +356,23 @@
return ranges
@staticmethod
- def __disjoint_ranges_from_key_set(key_set):
+ def __disjoint_ranges_from_key_set(encoding, key_set):
if not key_set:
return []
range_map = {}
for x in key_set:
assert not x.__is_unique()
- assert x != TransitionKey.epsilon
+ assert x != TransitionKey.epsilon()
for r in x.__ranges:
if not r[0] in range_map:
range_map[r[0]] = []
range_map[r[0]].append(r[1])
- ranges = TransitionKey.__disjoint_keys(range_map)
- TransitionKey.__verify_ranges(ranges, False)
+ ranges = TransitionKey.__disjoint_keys(encoding, range_map)
+ TransitionKey.__verify_ranges(encoding, ranges, False)
return ranges
@staticmethod
- def disjoint_keys(key_set):
+ def disjoint_keys(encoding, key_set):
'''Takes a set of possibly overlapping TransitionKeys, returns a list
of
TransitionKeys which don't overlap and whose union is the same as the
union
of the original key_set. In addition, TransitionKeys are not merged,
only
@@ -344,44 +381,44 @@
For example, if key_set contains two TransitionKeys for ranges [1-10]
and
[5-15], disjoint_keys returns a set of three TransitionKeys: [1-4],
[5-10],
[11-16].'''
- ranges = TransitionKey.__disjoint_ranges_from_key_set(key_set)
- return map(lambda x : TransitionKey([x]), ranges)
+ ranges = TransitionKey.__disjoint_ranges_from_key_set(encoding,
key_set)
+ return map(lambda x : TransitionKey(encoding, [x]), ranges)
@staticmethod
- def inverse_key(key_set):
+ def inverse_key(encoding, key_set):
'''Returns a TransitionKey which matches represents the inverse of the
union
of 'key_set'. The TransitionKeys contain a set of character ranges and
a set
of classes. The character ranges are inverted in relation to the
latin_1
character range, and the character classes are inverted in relation to
all
character classes in __class_bounds.'''
- ranges = TransitionKey.__disjoint_ranges_from_key_set(key_set)
- inverse = TransitionKey.__invert_ranges(ranges)
+ ranges = TransitionKey.__disjoint_ranges_from_key_set(encoding,
key_set)
+ inverse = TransitionKey.__invert_ranges(encoding, ranges)
if not inverse:
return None
- return TransitionKey(inverse)
+ return TransitionKey(encoding, inverse)
@staticmethod
- def __key_from_ranges(invert, ranges):
+ def __key_from_ranges(encoding, invert, ranges):
range_map = {}
for r in ranges:
if not r[0] in range_map:
range_map[r[0]] = []
range_map[r[0]].append(r[1])
- ranges = TransitionKey.__disjoint_keys(range_map)
- ranges = TransitionKey.__merge_ranges(ranges)
+ ranges = TransitionKey.__disjoint_keys(encoding, range_map)
+ ranges = TransitionKey.__merge_ranges(encoding, ranges)
if invert:
- ranges = TransitionKey.__invert_ranges(ranges)
- return TransitionKey(ranges)
+ ranges = TransitionKey.__invert_ranges(encoding, ranges)
+ return TransitionKey(encoding, ranges)
@staticmethod
- def __merge_ranges(ranges):
+ def __merge_ranges(encoding, ranges):
merged = []
last = None
for r in ranges:
assert not TransitionKey.__is_unique_range(r)
if last == None:
last = r
- elif (last[1] + 1 == r[0] and not TransitionKey.__is_class_range(r)):
+ elif (last[1] + 1 == r[0] and not encoding.is_class_range(r)):
last = (last[0], r[1])
else:
merged.append(last)
@@ -391,35 +428,76 @@
return merged
@staticmethod
- def merged_key(keys):
+ def merged_key(encoding, keys):
f = lambda acc, key: acc + list(key.__ranges)
- return TransitionKey.__key_from_ranges(False, reduce(f, keys, []))
+ return TransitionKey.__key_from_ranges(encoding, False, reduce(f,
keys, []))
@staticmethod
- def __invert_ranges(ranges):
+ def __invert_ranges(encoding, ranges):
inverted = []
last = None
- # Extract character classes (as opposed to character ranges) from
- # __class_bounds. Since latin_1 is the only real character range, we
can do
- # this.
- classes = set(TransitionKey.__class_bounds.values())
- latin_1 = TransitionKey.__class_bounds['latin_1']
- classes.remove(latin_1)
+ classes = set(encoding.class_value_iter())
for r in ranges:
assert not TransitionKey.__is_unique_range(r)
- if TransitionKey.__is_class_range(r):
+ if encoding.is_class_range(r):
classes.remove(r)
continue
if last == None:
- if r[0] != TransitionKey.__lower_bound:
- inverted.append((TransitionKey.__lower_bound, r[0] - 1))
+ if r[0] != encoding.lower_bound():
+ inverted.append((encoding.lower_bound(), r[0] - 1))
elif last[1] + 1 < r[0]:
inverted.append((last[1] + 1, r[0] - 1))
last = r
- upper_bound = latin_1[1]
+ upper_bound = encoding.primary_range()[1]
if last == None:
- inverted.append(latin_1)
+ inverted.append(encoding.primary_range())
elif last[1] < upper_bound:
inverted.append((last[1] + 1, upper_bound))
inverted += list(classes)
return inverted
+
+class Latin1Encoding(KeyEncoding):
+
+ def __init__(self):
+ super(Latin1Encoding, self).__init__(
+ 'latin1',
+ (1, 255),
+ ['eos', 'zero', 'byte_order_mark'])
+ self.add_predefined_range(
+ 'whitespace', [(9, 9), (11, 12), (32, 32), (133, 133), (160, 160)])
+ self.add_predefined_range(
+ 'letter', [
+ (65, 90), (97, 122), (170, 170), (181, 181),
+ (186, 186), (192, 214), (216, 246), (248, 255)])
+ self.add_predefined_range('line_terminator', [(10, 10), (13, 13)])
+ self.add_predefined_range(
+ 'identifier_part_not_letter', [(48, 57), (95, 95)])
+
+class Utf16Encoding(KeyEncoding):
+
+ def __init__(self):
+ super(Utf16Encoding, self).__init__(
+ 'utf16',
+ (1, 255),
+ ['eos', 'zero', 'byte_order_mark',
+ 'non_latin_1_whitespace',
+ 'non_latin_1_letter',
+ 'non_latin_1_identifier_part_not_letter',
+ 'non_latin_1_line_terminator',
+ 'non_latin_1_everything_else'])
+ self.add_predefined_range(
+ 'whitespace',
+ [(9, 9), (11, 12), (32, 32), (133, 133), (160, 160),
+ self.class_range('non_latin_1_whitespace')])
+ self.add_predefined_range(
+ 'letter', [
+ (65, 90), (97, 122), (170, 170), (181, 181),
+ (186, 186), (192, 214), (216, 246), (248, 255),
+ self.class_range('non_latin_1_letter')])
+ self.add_predefined_range(
+ 'line_terminator',
+ [(10, 10), (13, 13),
self.class_range('non_latin_1_line_terminator')])
+ self.add_predefined_range(
+ 'identifier_part_not_letter',
+ [(48, 57), (95, 95),
+ self.class_range('non_latin_1_identifier_part_not_letter')])
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
