{"action":"created","issue":{"url":"https://api.github.com/repos/tc39/ecma262/issues/81","labels_url":"https://api.github.com/repos/tc39/ecma262/issues/81/labels{/name}","comments_url":"https://api.github.com/repos/tc39/ecma262/issues/81/comments","events_url":"https://api.github.com/repos/tc39/ecma262/issues/81/events","html_url":"https://github.com/tc39/ecma262/issues/81","id":110969536,"number":81,"title":"ecma262 lexical grammar","user":{"login":"mehdishojaei","id":2007598,"avatar_url":"https://avatars.githubusercontent.com/u/2007598?v=3","gravatar_id":"","url":"https://api.github.com/users/mehdishojaei","html_url":"https://github.com/mehdishojaei","followers_url":"https://api.github.com/users/mehdishojaei/followers","following_url":"https://api.github.com/users/mehdishojaei/following{/other_user}","gists_url":"https://api.github.com/users/mehdishojaei/gists{/gist_id}","starred_url":"https://api.github.com/users/mehdishojaei/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mehdishojaei/subscriptions","organizations_url":"https://api.github.com/users/mehdishojaei/orgs","repos_url":"https://api.github.com/users/mehdishojaei/repos","events_url":"https://api.github.com/users/mehdishojaei/events{/privacy}","received_events_url":"https://api.github.com/users/mehdishojaei/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2015-10-12T12:57:11Z","updated_at":"2015-10-12T13:21:26Z","closed_at":null,"body":"Why ecma262 lexical grammar is not a regular grammar (that can be represented via Regular Expressions)?"},"comment":{"url":"https://api.github.com/repos/tc39/ecma262/issues/comments/147397646","html_url":"https://github.com/tc39/ecma262/issues/81#issuecomment-147397646","issue_url":"https://api.github.com/repos/tc39/ecma262/issues/81","id":147397646,"user":{"login":"benjamingr","id":1315533,"avatar_url":"https://avatars.githubusercontent.com/u/1315533?v=3","gravatar_id":"","url":"https://api.github.com/users/benjamingr","html_url":"https://github.com/benjamingr","followers_url":"https://api.github.com/users/benjamingr/followers","following_url":"https://api.github.com/users/benjamingr/following{/other_user}","gists_url":"https://api.github.com/users/benjamingr/gists{/gist_id}","starred_url":"https://api.github.com/users/benjamingr/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/benjamingr/subscriptions","organizations_url":"https://api.github.com/users/benjamingr/orgs","repos_url":"https://api.github.com/users/benjamingr/repos","events_url":"https://api.github.com/users/benjamingr/events{/privacy}","received_events_url":"https://api.github.com/users/benjamingr/received_events","type":"User","site_admin":false},"created_at":"2015-10-12T13:21:26Z","updated_at":"2015-10-12T13:21:26Z","body":"Well, trivially because it needs to support context free semantics. For example, a classical example of a grammar that is context free grammar is:\r\n\r\n```\r\n{x | x is an expression containing `{` and `}` and the parenthesis match }\r\n```\r\n\r\nThat is, matching `{`s and `}` `}`s. It is trivial to construct a context free grammar for it, but it is impossible to build a regular expression that parses it. Namely, because otherwise it would violate the [pumping lemma](https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages) - there is a direct proof in [Sipser's introductory book](http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X) on the topic if you'd prefer that. Intuitively, the reason is that regular languages cannot count. \r\n\r\nNow that we covered that the language is not regular - note that under the alphabet containing only `{` and `}` only the expressions that are in the language are valid ECMAScript statements. Namely:\r\n\r\n```js\r\n{} // valid\r\n{{}} // valid\r\n{{}{}} // valid\r\n{{{}}} // valid\r\n{{{ // invalid\r\n}}} // invalid\r\n```\r\n\r\nAnd so on - so only words that are valid ECMAScript statements are in the langauge under that alphabet. That language isn't regular and it's a subset of ES created by limiting the alphabet so ECMAScript must not be regular too. \r\n\r\nOf course, you can parse ECMAScript with regular expressions that contain various additions. Note that most real programming languages do not have a regular grammar. "}}