Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The language of languages

matt.might.net

Post reply on HN
Print view View original

11–20 of 20 posts

Re: The language of languages

#11

Post by aaronblohowiak »

seanmcdirmid wrote: post #9
JCraig wrote: post #3

I was thrown off by Might stating that "a grammar defines a language," which is not nearly as useful or factual as saying that it "describes" a language, the wording that he relies on throughout the rest of the article. That is the difference between me being able to make a dog or identify a dog based on a set of characteristics. Grammars are only one part of understanding a language, hardly the "language of language…

Ya, grammar only describes the syntax of a language. You still have the semantics and pragmatics to consider! I'm not even sure if a XBNF is the best way to describe or reason about language syntax. Precedence grammars (with hacks to handle braces) are quite interesting for robust error tolerant parsing, and might more closely mirror how we internal grammars in our head.

Technically, the grammar describes the language of the language, where the "language of the language" means the formal language, the set of characters and strings that are valid (wheras the union of all of the characters allowed in every char or string that is valid in the language is the language's alphabet, not all members of the alphabet may be allowed to stand alone as a token in a given language..)

Re: The language of languages

#12

Post by aaronblohowiak »

tlarkworthy wrote: post #4

I just worked with a mathematician who understood grammars, and could write one, but could not use the theory in any practical way. Parsing is not just recognition. You need to pass info up the parse tree so that after parsing, you have a new data structure with everything nicely structured ready to ACT UPON . People write in specific languages to achieve something, not to simply create syntactically correct bodies o…

>You need to pass info up the parse tree so that after parsing, you have a new data structure with everything nicely structured ready to ACT UPON.

I (and many others) prefer to keep these passes relatively distinct. Parse tree -> AST -> Internal Representation -> (Generation of Output / Interpretation)

Re: The language of languages

#14

Post by pacaro »

aaronblohowiak wrote: post #13

Cool tutorial and introduction. In my toy languages, I prefer PEGs to CFGs because I believe in ordinal precedence of choice -- this means that your grammar can NOT be ambiguous. I also enjoy that you can skip tokenization.

I too am a fan of PEG (Parsing Expression Grammar [1]), in particular I like that it is pretty easy to write a PEG parser, whereas there is a lot more work and housekeeping (IMHO) in implementing an LALR[2] parser.

I find it interesting that the parser generators are so closely bound up with code generation. I like the model where you can specify at runtime: when this non-terminal is parsed, execute that function.

[1] http://en.wikipedia.org/wiki/Parsing_expression_grammar [2] http://en.wikipedia.org/wiki/LALR_parser

Re: The language of languages

#15

Post by ilaksh »

Why is there no machine-processable language of languages?

Like a KR or some system that could read BNF or whatever and translate directly into another level, like operations defined by the operating system or something.

Why can't we describe a language declaratively and semantically so that its low level details wouldn't have to be specified manually and so that it could be related to other languages and reasoning could be done about its effects?

The lowest levels of the system would probably have to be described as part of the same representation system.

Re: The language of languages

#16

Post by phinnaeus »

ilaksh wrote: post #15

Why is there no machine-processable language of languages? Like a KR or some system that could read BNF or whatever and translate directly into another level, like operations defined by the operating system or something. Why can't we describe a language declaratively and semantically so that its low level details wouldn't have to be specified manually and so that it could be related to other languages and reasoning c…

Something like an interpreter / compiler generator?

Re: The language of languages

#17

Post by 6ren »

JCraig wrote: post #3

I was thrown off by Might stating that "a grammar defines a language," which is not nearly as useful or factual as saying that it "describes" a language, the wording that he relies on throughout the rest of the article. That is the difference between me being able to make a dog or identify a dog based on a set of characteristics. Grammars are only one part of understanding a language, hardly the "language of language…

A "language" in this context, is a set of strings. (a string is a sequence of symbols, e.g. a program). A grammar defines a language. For example, the regular grammar

  (a|b)(x|y)
defines the language

  {"ax", "ay", "bx", "by"}
Unfortunately, the term "language" has other meanings. There's human languages, like English. There's also programming languages, like lisp, python, java. And markup languages like HTML and XML. And other computer-related non-programming languages.

While it's true that these other languages have more to them than their syntax, they do define a "language" in the above initial sense: the set of all valid instances of it (i.e. without syntax errors), the set of sequences of symbols.

Programming languages generally include ways of extending their language (in the initial sense). Even java: a java program includes a syntax for extending its syntax (its "language"), in the sense that a program using a certain method invocation becomes valid, if that method is defined. Thus, it is itself both definitions of a grammar, and instances within that grammar - like XML and XSD combined in one (or XML and DTD).

BTW: this reply (and the two similar ones) will probably annoy you, because you know what a "formal language" is (at least, you use the term). I think your misinterpretation is that the article does not claim anything about "natural languages" - only the shape/structure of a language ("So, what shapes languages? Grammars do."/"Behind every language, there is a grammar that determines its structure.").

To be fair though, it then jumps straight into "A grammar defines a language.", without noting a shift in the meaning of the term "language". I think its meaning is clear from context, but it's certainly misleading to shift terminology as you go along!

Re: The language of languages

#18

Post by Yttrill »

ilaksh wrote: post #15

Why is there no machine-processable language of languages? Like a KR or some system that could read BNF or whatever and translate directly into another level, like operations defined by the operating system or something. Why can't we describe a language declaratively and semantically so that its low level details wouldn't have to be specified manually and so that it could be related to other languages and reasoning c…

Felix is built on an extensible parser which uses EBNF for the productions. The Felix "language" is defined in the library by such productions. The action codes of the grammar are arbitrary Scheme functions returning non-arbitrary s-expressions which map to Felix AST nodes.

The grammar is here:

http://felix-lang.org/lib/grammar

Close examination reveals even the regexps for literals are defined in the grammar. The parser is built on top of the excellent extensible GLR+ parsing tool Dypgen.

In principle the Felix parsing system is independent of Felix. All you need to do is replace the s-expression to Felix AST translator with some kind of pretty printer for s-expressions, even XML, and you can target anything.

Re: The language of languages

#19

Post by seanmcdirmid »

aaronblohowiak wrote: post #11
seanmcdirmid wrote: post #9

Earlier quoted context omitted.

Ya, grammar only describes the syntax of a language. You still have the semantics and pragmatics to consider! I'm not even sure if a XBNF is the best way to describe or reason about language syntax. Precedence grammars (with hacks to handle braces) are quite interesting for robust error tolerant parsing, and might more closely mirror how we internal grammars in our head.

Technically, the grammar describes the language of the language, where the "language of the language" means the formal language, the set of characters and strings that are valid (wheras the union of all of the characters allowed in every char or string that is valid in the language is the language's alphabet , not all members of the alphabet may be allowed to stand alone as a token in a given language..)

My PhD in PL tells me your right, but I'm always on the lookout for a more intuitional vs. technical definition of language, even for programming.

Re: The language of languages

#20

Post by aaronblohowiak »

seanmcdirmid wrote: post #19
aaronblohowiak wrote: post #11

Earlier quoted context omitted.

Technically, the grammar describes the language of the language, where the "language of the language" means the formal language, the set of characters and strings that are valid (wheras the union of all of the characters allowed in every char or string that is valid in the language is the language's alphabet , not all members of the alphabet may be allowed to stand alone as a token in a given language..)

My PhD in PL tells me your right, but I'm always on the lookout for a more intuitional vs. technical definition of language, even for programming.

You could always use META II which defines the grammar and the semantics :D
Post reply on HN