<p>This is a question about designing and implementing a language of street addresses.</p>
<blockquote>
<ul>
<li><p>In the input high-level interface language, many syntaxes are allowed.</p>
</li>
<li><p>In the output low-level implementation language, only one syntax for mailing addresses to to be allowed.</p>
</li>
</ul>
</blockquote>
<p>Many websites and cell-phone applications complain when human beings type in mailing addresses which do not conform to some pre-specified format.</p>
<p>For example, anytime I insert a dot (full-stop period character <code>.</code> (ASCII CODE 46⏨) into my mailing addresses, the front-end often displays an error message.</p>
<p>In theory, it is technologically feasible to parse a mailing address, standardize it, and then send the standardized mailing address to the back-end.</p>
<p>The following is an example of a mailing address:</p>
<pre><code>JANE DOE
IN CARE OF SILVIA SPLATHE
APARTMENT NUMBER 82
12709 EAST SESAME AVENUE
RANCHOS DE FICTIONAL CITY, COLORADO
80011 
United States of America
</code></pre>
<p>How can we ensure that end-users can type in any string <em><strong>shrt</strong></em>, such that:</p>
<blockquote>
<ol>
<li><p>There exists a verbose string <em><strong>v</strong></em> in the set of words such that <em><strong>shrt</strong></em> is a sub-sequence of the verbose string <em><strong>v</strong></em>.</p>
</li>
<li><p>There not exist two distinct strings <strong>verbose1</strong> and <strong>verbose2</strong> in the set such that <strong>shrt</strong> is a subsequence of both <strong>verbose1</strong> and <strong>verbose2</strong>. For example, people cannot type in <code>ST</code> for the cardinal direction because <code>ST</code> is a subsequence of both <code>WEST</code> and <code>EAST</code>)</p>
</li>
<li><p>the leftmost letter of <em><strong>shrt</strong></em> is the same as the leftmost letter in the unique matching verbose (long) string <strong>verbose</strong>. For example, <code>AVE</code> and <code>AVENUE</code> both begin with a letter <code>A</code>.</p>
</li>
</ol>
</blockquote>
<p>Note that a subsequence of the word <code>AVENUE</code> beginning with a letter <code>A</code> can be represented by the <a href="https://en.wikipedia.org/wiki/Regular_expression" rel="nofollow noreferrer">regular expression</a> <code>AV?E?N?U?E?</code></p>
<p>The idea would be that an end-user could type in almost any sub-sequence of a string such as <code>STREET.</code> and the output would be the standard abbreviation for street: <code>ST</code>.</p>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th>INPUT</th>
<th>OUTPUT</th>
</tr>
</thead>
<tbody>
<tr>
<td><code>STREET</code></td>
<td><code>ST</code></td>
</tr>
<tr>
<td><code>ST</code></td>
<td><code>ST</code></td>
</tr>
<tr>
<td><code>STREET.</code></td>
<td><code>ST</code></td>
</tr>
<tr>
<td><code>ST.</code></td>
<td><code>ST</code></td>
</tr>
<tr>
<td><code>SRT</code></td>
<td><code>ST</code></td>
</tr>
<tr>
<td><code>SRET</code></td>
<td><code>ST</code></td>
</tr>
</tbody>
</table>
</div>
<p>However, I am just trying to convey an idea. My question is, what approach would you use to implement a parser for street addresses which allows many different abbreviations for words like <code>STREET</code>?</p>

<parsing>
What kind of a lexer (tokenizer) and parser would be useful for standardizing mailing addresses?
CC BY-SA 4.0
2023-06-04T22:18:58.540Z
This question doesn't seem to be about programming languages ─ standardising mailing addresses is a pretty difficult problem and you can only really do it if you have a database of valid addresses. My previous address was like `125B Foo Road`, but the other address at that number was `125 Foo Road`, not `125A`. But the only way any software would know to correct `125A` to `125` is if it had a list of valid addresses on that road, and the subjective knowledge that `125A` is probably meant to be `125` rather than `125B`.
kaya3
CC BY-SA 4.0
2023-06-04T22:26:30.270Z
@kaya3 street addresses are easy compared to applying the same idea to programming languages. For example, if you wrote a pre-compiler for python, Java, or C# it would be nice if `def`, `define`, `dfn`, `dfne` and other sub-sequence of the word `define` all became simply `def`. This behavior would be scope sensitive, not global. If a class `Rectangle` has a member variable named `surface_area` we replace `Rectangle.sa` and `Rectangle.srfc_ara` with `Rectangle.surface_area`.
Samuel Muldoon
CC BY-SA 4.0
2023-06-04T22:28:30.440Z
This seems to be really the distinct subsequences problem: for each initial letter, take all the words starting with it and generate the sets of all distinct subsequences of each, then across all such sets for that letter remove all entries existing in more than one set, and associate each remaining subsequence with the canonical version. After that, it's just straight substring replacement with that pregenerated mapping; there's not really any lexing or parsing here. Does that align with what you're thinking of? If so, it's probably not really a match for *this* site.
Michael Homer
CC BY-SA 4.0
2023-06-04T22:30:31.920Z
@kaya3 When a class is defined that the class methods be given long self-documenting names. for example, `Rectangle.get_surface_area()`. However, a function-call or invocation could use almost any subsequence of a longer more verbose method name. A function invocation `Rectangle.get_sa()` would do the same thing as `Rectangle.get_surface_area()`. Most code is abbreviations only (e.g. `get_sa`). A language could be created where definitions of class methods have no abbreviated English words, but invocations are short and easy to type. The method is defined once, but called many times.
Samuel Muldoon
CC BY-SA 4.0
2023-06-04T22:34:47.210Z
@MichaelHomer If you would re-post your comment with a little more detail added, it would probably make a good answer to the question. My question is about programming languages, I am not sure why you think it's not about programming languages. I am thinking that a parser for a language similar, but different, than python could allow users to type many different sub-sequences of `str.leftjustify`. For example, we allow `str.ljust` and `str.leftjust` and `str.ljustify`.
Samuel Muldoon
CC BY-SA 4.0
2023-06-04T22:36:26.153Z
@MichaelHomer Some people have trouble memorizing the spellings of thousands of strange abbreviations. As such, a parser, interpreter, and/or compiler might allow different subsequences of class method names inside of a programming language. We could write `knode.parent` or `knode.par` or `knode.p` or any subsequence of the name of the class attribute, member variable, or class method defined inside of the original class.
Samuel Muldoon
CC BY-SA 4.0
2023-06-04T22:47:12.143Z
If your intention is to ask about this applied to keywords and names used in programming languages, then the question should ask about that. Contrary to your claim, this problem is *much* easier to solve in the context of a programming language than a natural language, even a restricted subset of a natural language such as street addresses ─ because programming languages have strict formal grammars, and natural languages don't. For example, you mention cardinal directions; I would challenge you to formalise a rule for whether or not the next word in an address should be a cardinal direction.
kaya3
CC BY-SA 4.0
2023-06-04T22:54:42.003Z
Well, that's what I was trying to sort out, the question title is "what sort of lexer or parser" but it doesn't seem to be about lexing or parsing but more just generating the subsequences, so I don't think my comment would be an on-topic answer.
Michael Homer
CC BY-SA 4.0
2023-06-04T22:57:35.357Z
*"My question is about programming languages, I am not sure why you think it's not about programming languages."* ─ perhaps because the question says *"This is a question about designing and implementing a language of street addresses"* and *"My question is, what approach would you use to implement a parser for street addresses ..."*, and there is no mention of programming languages in the question. I get the impression you decided to ask about street addresses because you thought that would be easier, but it is not easier, it just means nobody knows what you really want.
kaya3
CC BY-SA 4.0
2023-06-05T08:44:55.600Z
This is about parsing a DSL. Its a very limited in scope DSL but aren't questions about parsing on topic?
Bruce Adams
CC BY-SA 4.0
2023-06-05T11:09:29.413Z
@BruceAdams Mailing addresses aren't a DSL, they're a subset of natural language with no formal grammar. If the question is edited to include a formal grammar ─ or, better, edited to be about programming languages, as the OP has said in comments that it is supposed to be ─ then the question can be reopened.
kaya3
<p>If I understand what you want correctly:</p>
<ul>
<li>There is a fixed set of known words that you want to abbreviate.</li>
<li>Ambiguous abbreviations between words are prohibited.</li>
<li>Each abbreviation must start with the initial letter of the full word.</li>
<li>Characters must appear in order within the abbreviation.</li>
</ul>
<p>Any kind of lexer or parser can be used here, because this problem is not related to lexing or parsing at all. It is simply about generating all the abbreviation strings and constructing a canonical mapping, then standard string replacement.</p>
<p>You can generate that canonical mapping by:</p>
<ul>
<li>Starting with an empty string→string map as your canonicalisation map.</li>
<li>For each initial letter, take all the words starting with that letter
<ul>
<li>For each word, generate the set of distinct subsequences of that word, preserving the initial letter; a subsequence is a string you can reach solely by deleting characters from the string. There are dynamic programming algorithms for this, but you can also just brute-force it once because you have a fixed set of strings.</li>
<li>Remove any abbreviation that exists in multiple of these sets.</li>
<li>For each remaining abbreviation, add it to the canonicalisation map mapping to the full-length string.</li>
</ul>
</li>
<li>By construction, the abbreviations do not overlap between initial letters, so the canonicalisation map contains unique entries, and it's complete now.</li>
</ul>
<p>After this, for the problem in the question it simply comes down to straightforward string replacement: for each abbreviation, replace it as a whole word with the canonical form. This is a transformation that could be applied on the source as described.</p>
<p>If something like this were being used within a programming language to allow arbitrary contractions of function or method names, as you've suggested in the comments, it could also be applied post-parsing to canonicalise function calls. In this case, the set of words is the set of all function names, or the sets of methods existing on each static type, and you might run the algorithm multiple times.</p>
<p>In theory, you can generate a grammar from this also, with productions for each canonical form and each abbreviation as a terminal, but at least in the scenarios you have described this is not useful. Any finite set of strings defines a regular language, so you could also generate a regular expression for each mechanically if desired.</p>
<p>This seems like a bad feature for a programming language as well, but some IDEs do provide similar functionality for autocompletion shortcuts and might follow this sort of approach. They may also use something like the Damerau-Levenshtein distance to detect other typographical errors.</p>
<p>That covers things as far as I can make it about programming language design and implementation. Questions about general algorithms themselves are a better fit for the CS site, and about implementation of them for Stack Overflow.</p>

CC BY-SA 4.0
2023-06-04T23:48:05.730Z
2023-06-04T23:48:05.730Z
Michael Homer
# What kind of a lexer (tokenizer) and parser would be useful for standardizing mailing addresses?
Posted by: username_0 on 2023-06-04
This is a question about designing and implementing a language of street addresses.


In the input high-level interface language, many syntaxes are allowed.

In the output low-level implementation language, only one syntax for mailing addresses to to be allowed.



Many websites and cell-phone applications complain when human beings type in mailing addresses which do not conform to some pre-specified format.
For example, anytime I insert a dot (full-stop period character . (ASCII CODE 46⏨) into my mailing addresses, the front-end often displays an error message.
In theory, it is technologically feasible to parse a mailing address, standardize it, and then send the standardized mailing address to the back-end.
The following is an example of a mailing address:
JANE DOE
IN CARE OF SILVIA SPLATHE
APARTMENT NUMBER 82
12709 EAST SESAME AVENUE
RANCHOS DE FICTIONAL CITY, COLORADO
80011 
United States of America

How can we ensure that end-users can type in any string shrt, such that:


There exists a verbose string v in the set of words such that shrt is a sub-sequence of the verbose string v.

There not exist two distinct strings verbose1 and verbose2 in the set such that shrt is a subsequence of both verbose1 and verbose2. For example, people cannot type in ST for the cardinal direction because ST is a subsequence of both WEST and EAST)

the leftmost letter of shrt is the same as the leftmost letter in the unique matching verbose (long) string verbose. For example, AVE and AVENUE both begin with a letter A.



Note that a subsequence of the word AVENUE beginning with a letter A can be represented by the regular expression AV?E?N?U?E?
The idea would be that an end-user could type in almost any sub-sequence of a string such as STREET. and the output would be the standard abbreviation for street: ST.




INPUT
OUTPUT




STREET
ST


ST
ST


STREET.
ST


ST.
ST


SRT
ST


SRET
ST




However, I am just trying to convey an idea. My question is, what approach would you use to implement a parser for street addresses which allows many different abbreviations for words like STREET?
**Tags:** parsing
> **Comments:**
> **username_1**: This question doesn't seem to be about programming languages ─ standardising mailing addresses is a pretty difficult problem and you can only really do it if you have a database of valid addresses. My previous address was like `125B Foo Road`, but the other address at that number was `125 Foo Road`, not `125A`. But the only way any software would know to correct `125A` to `125` is if it had a list of valid addresses on that road, and the subjective knowledge that `125A` is probably meant to be `125` rather than `125B`.  
> **username_0**: @kaya3 street addresses are easy compared to applying the same idea to programming languages. For example, if you wrote a pre-compiler for python, Java, or C# it would be nice if `def`, `define`, `dfn`, `dfne` and other sub-sequence of the word `define` all became simply `def`. This behavior would be scope sensitive, not global. If a class `Rectangle` has a member variable named `surface_area` we replace `Rectangle.sa` and `Rectangle.srfc_ara` with `Rectangle.surface_area`.  
> **username_2**: This seems to be really the distinct subsequences problem: for each initial letter, take all the words starting with it and generate the sets of all distinct subsequences of each, then across all such sets for that letter remove all entries existing in more than one set, and associate each remaining subsequence with the canonical version. After that, it's just straight substring replacement with that pregenerated mapping; there's not really any lexing or parsing here. Does that align with what you're thinking of? If so, it's probably not really a match for *this* site.  
> **username_0**: @kaya3 When a class is defined that the class methods be given long self-documenting names. for example, `Rectangle.get_surface_area()`. However, a function-call or invocation could use almost any subsequence of a longer more verbose method name. A function invocation `Rectangle.get_sa()` would do the same thing as `Rectangle.get_surface_area()`. Most code is abbreviations only (e.g. `get_sa`). A language could be created where definitions of class methods have no abbreviated English words, but invocations are short and easy to type. The method is defined once, but called many times.  
> **username_0**: @MichaelHomer If you would re-post your comment with a little more detail added, it would probably make a good answer to the question. My question is about programming languages, I am not sure why you think it's not about programming languages. I am thinking that a parser for a language similar, but different, than python could allow users to type many different sub-sequences of `str.leftjustify`. For example, we allow `str.ljust` and `str.leftjust` and `str.ljustify`.  
> **username_0**: @MichaelHomer Some people have trouble memorizing the spellings of thousands of strange abbreviations. As such, a parser, interpreter, and/or compiler might allow different subsequences of class method names inside of a programming language. We could write `knode.parent` or `knode.par` or `knode.p` or any subsequence of the name of the class attribute, member variable, or class method defined inside of the original class.  
> **username_1**: If your intention is to ask about this applied to keywords and names used in programming languages, then the question should ask about that. Contrary to your claim, this problem is *much* easier to solve in the context of a programming language than a natural language, even a restricted subset of a natural language such as street addresses ─ because programming languages have strict formal grammars, and natural languages don't. For example, you mention cardinal directions; I would challenge you to formalise a rule for whether or not the next word in an address should be a cardinal direction.  
> **username_2**: Well, that's what I was trying to sort out, the question title is "what sort of lexer or parser" but it doesn't seem to be about lexing or parsing but more just generating the subsequences, so I don't think my comment would be an on-topic answer.  
> **username_1**: *"My question is about programming languages, I am not sure why you think it's not about programming languages."* ─ perhaps because the question says *"This is a question about designing and implementing a language of street addresses"* and *"My question is, what approach would you use to implement a parser for street addresses ..."*, and there is no mention of programming languages in the question. I get the impression you decided to ask about street addresses because you thought that would be easier, but it is not easier, it just means nobody knows what you really want.  
> **username_3**: This is about parsing a DSL. Its a very limited in scope DSL but aren't questions about parsing on topic?  
> **username_1**: @BruceAdams Mailing addresses aren't a DSL, they're a subset of natural language with no formal grammar. If the question is edited to include a formal grammar ─ or, better, edited to be about programming languages, as the OP has said in comments that it is supposed to be ─ then the question can be reopened.  
---
## 1 answers
### Answer by username_2 on 2023-06-04. Score: 3
If I understand what you want correctly:

* There is a fixed set of known words that you want to abbreviate.
* Ambiguous abbreviations between words are prohibited.
* Each abbreviation must start with the initial letter of the full word.
* Characters must appear in order within the abbreviation.

Any kind of lexer or parser can be used here, because this problem is not related to lexing or parsing at all. It is simply about generating all the abbreviation strings and constructing a canonical mapping, then standard string replacement.

You can generate that canonical mapping by:

* Starting with an empty string→string map as your canonicalisation map.
* For each initial letter, take all the words starting with that letter
  + For each word, generate the set of distinct subsequences of that word, preserving the initial letter; a subsequence is a string you can reach solely by deleting characters from the string. There are dynamic programming algorithms for this, but you can also just brute-force it once because you have a fixed set of strings.
  + Remove any abbreviation that exists in multiple of these sets.
  + For each remaining abbreviation, add it to the canonicalisation map mapping to the full-length string.
* By construction, the abbreviations do not overlap between initial letters, so the canonicalisation map contains unique entries, and it's complete now.

After this, for the problem in the question it simply comes down to straightforward string replacement: for each abbreviation, replace it as a whole word with the canonical form. This is a transformation that could be applied on the source as described.

If something like this were being used within a programming language to allow arbitrary contractions of function or method names, as you've suggested in the comments, it could also be applied post-parsing to canonicalise function calls. In this case, the set of words is the set of all function names, or the sets of methods existing on each static type, and you might run the algorithm multiple times.

In theory, you can generate a grammar from this also, with productions for each canonical form and each abbreviation as a terminal, but at least in the scenarios you have described this is not useful. Any finite set of strings defines a regular language, so you could also generate a regular expression for each mechanically if desired.

This seems like a bad feature for a programming language as well, but some IDEs do provide similar functionality for autocompletion shortcuts and might follow this sort of approach. They may also use something like the Damerau-Levenshtein distance to detect other typographical errors.

That covers things as far as I can make it about programming language design and implementation. Questions about general algorithms themselves are a better fit for the CS site, and about implementation of them for Stack Overflow.
---
