Error recovery is an essential feature for a parser that should be plugged in Integrated Development Environments (IDEs), which must build Abstract Syntax Trees (ASTs) even for syntactically invalid programs in order to offer features such as automated refactoring and code completion. Parsing Expressions Grammars (PEGs) are a formalism that naturally describes recursive top-down parsers using a restricted form of backtracking. Labeled failures are a conservative extension of PEGs that adds an error reporting mechanism for PEG parsers, and these labels can also be associated with recovery expressions to provide an error recovery mechanism. These expressions can use the full expressivity of PEGs to recover from syntactic errors. Manually annotating a large grammar with labels and recovery expressions can be difficult. In this work, we present algorithms that automatically annotates a PEG with labels, and build their corresponding recovery expressions. We evaluate these algorithms by using them to generate error recovering parsers for four programming languages: Titan, Pascal, C and Java. The results show that with a small amount of manual intervention our approach can be used to produce error recovering parsers for PEGs where most choices have alternatives with disjoint FIRST sets.
The error recovery approach for predictive top-down parsers proposed by Wirth @cite_14 was a major influence for several tools. In Wirth's approach, when there is an error during the matching of a non-terminal @math , we try to synchronize by using the symbols that can follow @math plus the symbols that can follow any non-terminal @math that we are currently trying to match (the procedure associated with @math is on the stack). Moreover, the tokens which indicate the beginning of a structured element (e.g., while , if ) or the beginning of a declaration (e.g., var , function ) are used to synchronize with the input.
@cite_14
2003494253
We propose a novel transition-based algorithm that straightforwardly parses sentences from left to right by building @math attachments, with @math being the length of the input sentence. Similarly to the recent stack-pointer parser by (2018), we use the pointer network framework that, given a word, can directly point to a position from the sentence. However, our left-to-right approach is simpler than the original top-down stack-pointer parser (not requiring a stack) and reduces transition sequence length in half, from 2 @math -1 actions to @math . This results in a quadratic non-projective parser that runs twice as fast as the original while achieving the best accuracy to date on the English PTB dataset (96.04 UAS, 94.43 LAS) among fully-supervised single-model dependency parsers, and improves over the former top-down transition system in the majority of languages tested. Motivated by applications in blockchains and sensor networks, we consider a model of @math nodes trying to reach consensus on their majority bit. Each node @math is assigned a bit at time zero, and is a finite automaton with @math bits of memory (i.e., @math states) and a Poisson clock. When the clock of @math rings, @math can choose to communicate, and is then matched to a uniformly chosen node @math . The nodes @math and @math may update their states based on the state of the other node. Previous work has focused on minimizing the time to consensus and the probability of error, while our goal is minimizing the number of communications. We show that when @math , consensus can be reached at linear communication cost, but this is impossible if @math . We also study a synchronous variant of the model, where our upper and lower bounds on @math for achieving linear communication cost are @math and @math , respectively. A key step is to distinguish when nodes can become aware of knowing the majority bit and stop communicating. We show that this is impossible if their memory is too low. We consider codes over fixed alphabets against worst-case symbol deletions. For any fixed @math , we construct a family of codes over alphabet of size @math with positive rate, which allow efficient recovery from a worst-case deletion fraction approaching @math . In particular, for binary codes, we are able to recover a fraction of deletions approaching @math . Previously, even non-constructively the largest deletion fraction known to be correctable with positive rate was @math , and around @math for the binary case. Our result pins down the largest fraction of correctable deletions for @math -ary codes as @math , since @math is an upper bound even for the simpler model of erasures where the locations of the missing symbols are known. Closing the gap between @math and @math for the limit of worst-case deletions correctable by binary codes remains a tantalizing open question. Neighbor discovery is one of the first steps in the initialization of a wireless ad hoc network. In this paper, we design and analyze practical algorithms for neighbor discovery in wireless networks. We first consider an ALOHA-like neighbor discovery algorithm in a synchronous system, proposed in an earlier work. When nodes do not have a collision detection mechanism, we show that this algorithm reduces to the classical Coupon Collector's Problem . Consequently, we show that each node discovers all its @math neighbors in an expected time equal to @math , for some constant @math . When nodes have a collision detection mechanism, we propose an algorithm based on receiver status feedback which yields a @math improvement over the ALOHA-like algorithm. Our algorithms do not require nodes to have any estimate of the number of neighbors. In particular, we show that not knowing @math results in no more than a factor of two slowdown in the algorithm performance. In the absence of node synchronization, we develop asynchronous neighbor discovery algorithms that are only a factor of two slower than their synchronous counterparts. We show that our algorithms can achieve neighbor discovery despite allowing nodes to begin execution at different time instants. Furthermore, our algorithms allow each node to detect when to terminate the neighbor discovery phase.