{'fraction_non_alphanumeric': 0.031538461538461536, 'fraction_numerical': 0.0, 'mean_word_length': 5.4405940594059405, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Parsing Contextual Grammars with Linear, Regular and Context-Free Selectors

Contextual Grammars (CGs) provide an appropriate description of natural languages. Unfortunately, no parser which runs in polynomial time was known for some linguistically relevant classes. In this paper, an intertwined two–level Earley–based parser for CGs with finite, regular and context–free selectors is presented. In both phases context–free grammars are defined which identify individual selectors and contexts in the input string and which find context–selector pairs. The Earley algorithms provides an efficient data structure to exchange the results between the two phases (i.e. phase one −→ phase two: contexts and selectors, phase two −→ phase one: erased contexts according to a production) and to reuse intermedidate results effectively when repeatingly new contexts and selectors are predicted for each removed context in the input string and consequently new productions are identified. As we deploy a polynomial parser for CGs with context–free selectors, the linguistic relevance of this family of languages (i.e. CLα(CF )) is discussed here. We show that some center–embedded phenomena which cannot be generated by a CG with regular selectors according to the recursion definition Mg belong to CLMg(CF ).