2

According to the question Why did DOS use dollar-terminated strings? DOS uses dollar-terminated strings, inherited from CP/M which used them because DEC also used dollar as the string terminator.

However, DOS is not the only context where dollar is a string terminator. It is well-known that parsing theory within computer science also uses dollar as a special character meaning the end of input. As an example, the Wikipedia page about LL parsing refers to $ as the end of input: https://en.wikipedia.org/wiki/LL_parser#Parser

Is there any connection in the use of the dollar sign as the end of string in DOS and the end of input in parsing theory? If there is a connection, which one was first: parsing theory? Or DOS / CP/M / DEC?

Improve this question
1
  • 1
    Also, $ marks the end of line in a regular expression.
    – JeanPierre
    Oct 14, 2018 at 21:15

3 Answers 3

Reset to default
3

It is basically any character that is not part of the syntax. There is no connection with parsing theory. It depends on the definition of what is being parsed. $ is usually used to reference the stack. The LL example just uses the $ to mean push into the stack.

In Principles of Compiler Design by Aho (1977), in the shift-reduce parsing example, $ is also used to mean push on the stack. In Compiler Construction for Digital Computers by Gries (1971), # is used for the same purpose.

$ was used for all sorts of things in languages.

  • In BASIC, it denotes strings
  • In BCPL it is a kind of bracket ($ and $)
  • In Intel Fortran (also MS, DEC and Compaq) it is a directive
  • In makefiles it is a variable or passed in parameter
  • In bash, TCL and DEC command language it is the value of a variable

The other commonly used ones are %, # and &

Improve this answer
2

It has already been mentioned that in "parsing theory", $ isn't necessarily used as the end-of-input marking.

However, Unix was developed first on DEC machines, esp. the PDP-11, and at that time results from parsing theory (e.g regular expressions) were implemented (e.g. grep). So it was natural to choose the end-of-input symbol DEC was already using, namely $. And that's still the case today.

This in turn probably influenced whoever wrote the wikipedia page to use $.

Improve this answer
2
  • While I'd point out that while $ isn't necessarily used as end of input in parsing theory texts, it is a very common convention ... But I'm not sure that the convention wasn't made mainstream by the extremely popular "dragon book" textbook, which was written by members of the same Bell Labs group as those who designed Unix, so possibly it came from the same source.
    – Jules
    Oct 14, 2018 at 11:12
  • 1
    @Jules: If you look at the original Chomsky papers, e.g. this one linked from Wikipedia dated 1959, there's no usage of $ (though he uses # as separator). The Dragon Book was first published 1986, that's a lot later, when PDP's weren't that popular anymore... And I certainly never thought of the $ usage as "mainstream convention", and yes, I read the Dragon Book (among various others that didn't use $).
    – dirkt
    Oct 14, 2018 at 15:11
1

In context of the description of LL-Parsers (and others) $ is not the $ character, but a symbol representing End of Input (EOI). It's a symbol like all the others within the set of formulas describing what a (LL) parser does.

If you take a look at the C example for such a parser, you'll easy see the lexer looking for a null char as the EOI character, not $:

        case '\0': return TS_EOS; // end of stack: the $ terminal symbol
Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .