recentpopularlog in


« earlier   
ACM Digital Library
Welcome to the ACM Digital Library

A community engaged with a repository of resources to support computing research and practice

Please explore and use the [Feedback] button on any page to help us shape the new site.
acm  library  research  computerscience  computing 
3 hours ago by maltodextrin
Thomas Fowler (inventor) - Wikipedia
In 1840 Fowler produced a mechanical calculating machine which operated using balanced ternary arithmetic.
fowler  ternary  computing  woodwork 
3 days ago by yorksranter
Semantics and Algorithms for Data-dependent Grammars
Traditional parser generation technologies are incapable of handling the demands of modern programmers. In this paper, we
present the design and theory of a new parsing engine, YAKKER,
capable of handling the requirements of modern applications including (1) full scannerless context-free grammars with (2) regular expressions as right-hand sides for defining nonterminals.
YAKKER also includes (3) facilities for binding variables to intermediate parse results and (4) using such bindings within arbitrary constraints to control parsing. These facilities allow the kind
of data-dependent parsing commonly needed in systems applications, particularly those that operate over binary data. In addition,
(5) nonterminals may be parameterized by arbitrary values, which
gives the system good modularity and abstraction properties in the
presence of data-dependent parsing. Finally, (6) legacy parsing libraries, such as sophisticated libraries for dates and times, may be
directly incorporated into parser specifications. We illustrate the
importance and utility of this rich format specification language by
presenting its use on examples ranging from difficult programming
language grammars to web server logs to binary data specification.
We also show that our grammars have important compositionality
properties and explain why such properties are important in modern
applications such as automatic grammar induction.
In terms of technical contributions, we provide a traditional
high-level semantics for our new grammar formalization and show
how to compile these grammars into nondeterministic automata.
These automata are stack-based, somewhat like conventional pushdown automata, but are also equipped with environments to track
data-dependent parsing state. We prove the correctness of our translation of data-dependent grammars into these new automata and
then show how to implement the automata efficiently using a variation of Earley’s parsing algorithm.
computing  parsing 
3 days ago by whitequark
Shift-Resolve Parsing: Simple, Unbounded Lookahead, Linear Time
This paper introduces a mechanism for combining unbounded lookahead exploration with linear time complexity in a deterministic parser.
The idea is to use a resolve parsing action in place of the classical reduce. The construction of shift-resolve parsers is presented as a two-step
algorithm, from the grammar to a finite nondeterministic automaton, and
from this automaton to the deterministic parser. Grammar classes comparisons are provided.
computing  parsing 
3 days ago by whitequark
Apollo 11 vs USB-C Chargers
"The CYPD4225 is definitely not rated for space. I have no idea if it would work in space."

This is fun, but also detailed. USB-PD chargers need a microcontroller to do power negotiation. So how powerful is a USB-C PD charger compared to, say, the Apollo 11 guidance computer? Forrest Heller goes into some detail - not just comparing clock speed, but also looking at memory, and clock-cycles per operation.
computing  usb  usbc  hardware  microcontrollers  computation  space 
3 days ago by infovore

Copy this bookmark:

to read